这是noip2008的第三题，前两题基本只要认真一点，都是送分。
多进程的动态规划题。
我是使用了四维的数组，完全可以AC，空间也可以承受。
对角线划分状态，可以优化到三维。
以下是我的代码：
#include<stdio.h>
#define max(a,b) (a>b?a:b)
typedef unsigned long Long;
Long d[52][52][52][52]=
{0};
int main()
{
Long m,n,a[52][52]={0};
Long i,j,i1,j1,i2,j2;
FILE *fin,*fout;
fin=fopen("message.in","r");
fscanf(fin,"%ld%ld",&m,&n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
fscanf(fin,"%ld",&a[i][j]);
fclose(fin);//------Read In
for(i1=1;i1<=m;i1++)
for(j1=1;j1<=n;j1++)
for(i2=1;i2<=m;i2++)
for(j2=1;j2<=n;j2++)
{
d[i1][j1][i2][j2]=max(d[i1-1][j1][i2-1][j2],d[i1-1][j1][i2][j2-1]);
d[i1][j1][i2][j2]=max(d[i1][j1][i2][j2],d[i1][j1-1][i2-1][j2]);
d[i1][j1][i2][j2]=max(d[i1][j1][i2][j2],d[i1][j1-1][i2][j2-1]);
if(i1==i2&&j1==j2)
d[i1][j1][i2][j2]+=a[i1][j1];
else d[i1][j1][i2][j2]+=a[i1][j1]+a[i2][j2];
}
fout=fopen("message.out","w");
fprintf(fout,"%ld\n",d[m][n][m][n]);
fclose(fout);
return 0;
}
posted on 2010-01-06 19:36
lee1r 阅读(324)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划