51nod 1084 矩阵取数问题 V2 dp

第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200)第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)Output
输出能够获得的最大价值。Input示例
3 31 3 32 1 32 2 1Output示例
17
#include<cstdio>#include<iostream>#define MAX(a,b,c,d) max(max(a,b),max(c,d))using namespace std;int n,m,a[201][201],dp[401][201][201]={0};int main(){	scanf("%d%d",&m,&n);	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	scanf("%d",&a[i][j]);	for(int k=2;k<=n+m;k++)	for(int i=1;i<=n&&k-i>0;i++)	for(int j=1;j<=n&&k-j>0;j++)		dp[k][i][j]=max(dp[k][i][j],		MAX(dp[k-1][i][j],dp[k-1][i-1][j-1],dp[k-1][i-1][j],dp[k-1][i][j-1])+a[i][k-i]+(i==j?0:a[j][k-j]));		PRintf("%d/n",dp[n+m][n][n]);	return 0;}