程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1050 二維動態規劃轉變成枚舉加一維的動態規劃！

POJ 1050 二維動態規劃轉變成枚舉加一維的動態規劃！

編輯：C++入門知識

POJ 1050 二維動態規劃轉變成枚舉加一維的動態規劃！

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 

using namespace std;

int n;
int a[105][105];
int dp[105][105];
int sum[105][105];


int main(){
	while(scanf("%d",&n)!=EOF){
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				scanf("%d",&a[i][j]);
			}
		}
		memset(dp,0,sizeof(dp));
	
		for(int j = 1;j <= n;j++){ // j列的前綴和 
			for(int i = 1;i <= n;i++){
				sum[j][i] = sum[j][i-1] + a[i][j];
			}
		}
		for(int i = 1;i <= n;i++){
			for(int j = i;j <= n;j++){
				int right = 0;
				for(int k = 1;k <= n;k++){
					 if(right >= 0){
					 	right += sum[k][j] - sum[k][i-1]; 
					 }
					 else{
					 	right = sum[k][j] - sum[k][i-1]; 
					 }
					 
					 dp[i][j] = max(dp[i][j],right);
					 
				} 
			}
		}		
		int ans = -INT_MAX;
		for(int i = 1;i <= n;i++){
			for(int j = i;j <= n;j++){
				if(dp[i][j] > ans){
					ans = dp[i][j];
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C++入門知識

C++, const：，const

C++, const：，const 問題：

圖總結之存儲結構代碼詳解

圖總結之存儲結構代碼詳解一、圖的存儲結構 1.1

C++中的指針用法匯集

在C++中，指針用得比較多，對於裡面眾多的指針用法，不免弄

在O(1)時間刪除鏈表結點，結點

在O(1)時間刪除鏈表結點，結點題目：給定單向鏈表的頭指針和

POJ2585 Window Pains，

POJ2585 Window Pains，Window Pa

stl中的空間配置器，stl空間配置器

stl中的空間配置器，stl空間配置器　一般我們習慣的c++