hdu_4826_Labyrinth_2014百度の星(dp)

タイトル接続:http://acm.hdu.edu.cn/showproblem.php?pid=4826
中国語の問題、説明しない
題名:dpはやって、第1列は上から下へ行くことしかできなくて、だから先に第1列のdpの配列を算出して、それから2つのdpの配列を開いて以下の上から下へと下から上へdpの値を計算して、最後に最大を取ってそのセルの最大値まで歩きます

#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
int a[101][101],dp1[101],dp2[101],t,n,m,ic=1;
int fuck(){
	for(int i=2;i<=m;i++)a[i][1]+=a[i-1][1];//    dp  
	for(int i=2;i<=n;i++){//    
		dp1[0]=dp2[0]=dp1[m+1]=dp2[m+1]=-99999999;
		//             ，     
		for(int j=m;j>=1;j--)
			dp1[j]=max(dp1[j+1],a[j][i-1])+a[j][i];
		for(int j=1;j<=m;j++)
			dp2[j]=max(dp2[j-1],a[j][i-1])+a[j][i];
		for(int j=1;j<=m;j++)
			a[j][i]=max(dp1[j],dp2[j]);
	}
	return a[1][n];
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&m,&n);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
		printf("Case #%d:
%d
",ic++,fuck());
	}
}