這是noip2008的第三題，前兩題基本只要認真一點，都是送分。
多進程的動態(tài)規(guī)劃題。
我是使用了四維的數(shù)組，完全可以AC，空間也可以承受。
對角線劃分狀態(tài)，可以優(yōu)化到三維。
以下是我的代碼：
#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 閱讀(343)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃