類似于“傳紙條”，直接從“傳紙條”的源代碼上修改的。
以下是我的代碼：
#include<stdio.h>
#define MAXN 51
#define max(a,b) (a>b?a:b)
long m,n,a[MAXN][MAXN],d[2][MAXN][MAXN][MAXN]=
{0};
long begin(long x)
{
if(x>=1&&x<=n) return 1;
if(x>n&&x<=n+m-1) return x-n+1;
}
long end(long x)
{
return (x<m?x:m);
}
int main()
{
long i,j,k,l;
scanf("%ld",&m);
n=m;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%ld",&a[i][j]);
// Read In
for(i=1;i<=n+m-1;i++)
for(j=begin(i);j<=end(i);j++)
for(k=begin(i);k<=end(i);k++)
for(l=begin(i);l<=end(i);l++)
{
d[i%2][j][k][l]=max(d[(i-1)%2][j][k][l],d[(i-1)%2][j][k][l-1]);
d[i%2][j][k][l]=max(d[i%2][j][k][l],d[(i-1)%2][j][k-1][l]);
d[i%2][j][k][l]=max(d[i%2][j][k][l],d[(i-1)%2][j][k-1][l-1]);
d[i%2][j][k][l]=max(d[i%2][j][k][l],d[(i-1)%2][j-1][k][l]);
d[i%2][j][k][l]=max(d[i%2][j][k][l],d[(i-1)%2][j-1][k][l-1]);
d[i%2][j][k][l]=max(d[i%2][j][k][l],d[(i-1)%2][j-1][k-1][l]);
d[i%2][j][k][l]=max(d[i%2][j][k][l],d[(i-1)%2][j-1][k-1][l-1]);
if(j!=k&&k!=l&&j!=l)
d[i%2][j][k][l]+=a[j][i-j+1]+a[k][i-k+1]+a[l][i-l+1];
else if(j!=k&&k==l)
d[i%2][j][k][l]+=a[j][i-j+1]+a[k][i-k+1];
else if(j==k&&k!=l)
d[i%2][j][k][l]+=a[j][i-j+1]+a[l][i-l+1];
else if(j==k&&k==l)
d[i%2][j][k][l]+=a[j][i-j+1];
}
printf("%ld\n",d[(n+m-1)%2][m][m][m]);
// getchar();getchar();
return 0;
}posted on 2010-01-06 20:34
lee1r 閱讀(228)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃