NOIP 2008 提高组 NOIP 2008 3.傳紙條
作法 : DP
有更好的3維作法 請大家自行搜尋
/***********************************************************/
#include<stdlib.h>
#include<stdio.h>
int N,M;
int map[51][51];
short f[51][51][51][51];
main()
{
scanf("%d %d",&N,&M);
{
int a,b,c;
for(a=1;a<=N;a++)
for(b=1;b<=M;b++)
scanf("%d",&map[a][b]);
int i,j,x,y;
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
for(x=1;x<=N;x++)
for(y=1;y<=M;y++)
{
int MAX;
MAX=(f[i-1][j][x-1][y]>f[i-1][j][x][y-1])?f[i-1][j][x-1][y]:f[i-1][j][x][y-1];
MAX=(MAX>f[i][j-1][x][y-1])?MAX:f[i][j-1][x][y-1];
MAX=(MAX>f[i][j-1][x-1][y])?MAX:f[i][j-1][x-1][y];
f[i][j][x][y]+=map[i][j]+MAX;
if(i!=x||j!=y)
f[i][j][x][y]+=map[x][y];
}
printf("%d\n",f[N][M][N][M]);
}
return 0;
}
/*
f[i][j][x][y]表示第一路到(i,j),第二路到(x,y)的好心度最大值。
*/