/*
状态：
设sum[j][k]表示以j为起始下标,连续的k个数的和
s为新的一行以j为起始下标,连续的k个数的和
动态转移方程：
sum[j][k]=max{sum[j][k]+s,s};
ans=max{sum[j][k]} (i=0 ~ n-1)
*/
#include <iostream>   
using namespace std;
int main(){   
    int n,i,j,k,a[105][105];
	int max=-10000,sum[105][105]={-10000};
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=0;j<n;j++)
			cin>>a[i][j];
		for(j=0;j<=n-1;j++){ //起始下标为j:0 ~ n-1
			int s=0;
			for(k=j;k<=n-1;k++){//对应求和下标0:0 ~ n-1 ;1:1 ~ n-1......n-1:n-1
				s += a[i][k];
				sum[j][k-j+1]=((s+sum[j][k-j+1] > s)?s+sum[j][k-j+1]:s);//动态转移方程
				if(sum[j][k-j+1] > max)	max=sum[j][k-j+1];
				//cout<<sum[j][k-j+1]<<" ";//为可打出sum[j][k-j+1]表示起始下标为j连续的k-j+1个数的和的矩阵
			}//cout<<endl;	
		}//cout<<endl;			
	}
	cout<<max<<endl;
	return 0;
} 

• Re:纪念我的第一次动态规划 一次AC的 (7) 0403100119 2011-07-22 15:43:42