Vijos P 1493メモ(ダブルスレッドDP)
1086 ワード
分析:この问题はその隠れた题意YYを出して、i+j=x+y、これを探し出すのは简単で、直接4次元を开いてDPに来て、
#include<stdio.h>
int dp[51][51][51][51];
int num[51][51];
int max(int a,int b,int c,int d)
{
if(a>b&&a>c&&a>d)return a;
if(b>a&&b>c&&b>d)return b;
if(c>b&&c>a&&c>d)return c;
return d;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&num[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int x=1;x<=n;x++)
{
int y=i+j-x;
if(i>x&&y>=0)
{
dp[i][j][x][y]=max(dp[i-1][j][x-1][y]+num[i][j]+num[x][y],dp[i-1][j][x][y-1]+num[i][j]+num[x][y],dp[i][j-1][x-1][y]+num[i][j]+num[x][y],dp[i][j-1][x][y-1]+num[i][j]+num[x][y]);
}
}
}
}
printf("%d
",dp[n][m-1][n-1][m]);
return 0;
}