二取：
传纸条：
O(N^4)
#include<cstdio>
using namespace std;
int N,M;
int a[51][51];
int f[51][51][51][51];
inline int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;++i)
for(int j=1;j<=M;++j)
scanf("%d",&a[i][j]);
for(int i=1;i<=N;++i)
for(int j=1;j<=M;++j)
for(int i1=1;i1<=N;++i1)
for(int j1=1;j1<=M;++j1){
f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i-1][j][i1-1][j1]);
f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i][j-1][i1][j1-1]);
f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i-1][j][i1][j1-1]);
f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i][j-1][i1-1][j1]);
f[i][j][i1][j1]+=a[i][j];
if(i!=i1&&j!=j1)
f[i][j][i1][j1]+=a[i1][j1];
}
printf("%d\n",f[N][M][N][M]);
return 0;
}
O（N^3)：
#include<cstdio>
using namespace std;
int N,M;
int a[51][51];
int f[110][51][51]={0};
int d[4][2]={-1,-1,0,-1,-1,0,0,0};
inline int min(int x,int y)
{
return x>y?y:x;
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;++i)
for(int j=1;j<=M;++j)
scanf("%d",&a[i][j]);
for(int k=1;k<N+M;++k)
for(int i1=1;i1<=min(k,N);++i1)
for(int i2=1;i2<=min(k,N);++i2){
int t=a[i1][k+1-i1]+a[i2][k+1-i2];
if(i1==i2) t=a[i1][k+1-i1];
for(int i=0;i<4;++i)
if(f[k][i1][i2]<f[k-1][i1+d[i][0]][i2+d[i][1]])
f[k][i1][i2]=f[k-1][i1+d[i][0]][i2+d[i][1]];
f[k][i1][i2]+=t;
}
printf("%d\n",f[N+M-1][N][N]);
return 0;
}
三取：
#include<cstdio>
using namespace std;
int N;
int a[21][21];
int f[45][21][21][21]={0};
int d[8][3]={-1,-1,-1,-1,-1,0,-1,0,-1,0,-1,-1,0,0,-1,0,-1,0,-1,0,0,0,0,0};
inline int min(int x,int y)
{
return x>y?y:x;
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
scanf("%d",&a[i][j]);
for(int k=1;k<2*N;++k)
for(int x1=1;x1<=min(k,N);++x1)
for(int x2=1;x2<=min(k,N);++x2)
for(int x3=1;x3<=min(k,N);++x3){
int t=a[x1][k+1-x1]+a[x2][k+1-x2]+a[x3][k+1-x3];
if(x1==x2&&x1!=x3) t=a[x1][k+1-x1]+a[x3][k+1-x3];
if(x1==x3&&x1!=x2) t=a[x1][k+1-x1]+a[x2][k+1-x2];
if(x2==x3&&x1!=x2) t=a[x1][k+1-x1]+a[x2][k+1-x2];
if(x1==x2&&x1==x3) t=a[x1][k+1-x1];
for(int i=0;i<8;++i)
if(f[k][x1][x2][x3]<f[k-1][x1+d[i][0]][x2+d[i][1]][x3+d[i][2]])
f[k][x1][x2][x3]=f[k-1][x1+d[i][0]][x2+d[i][1]][x3+d[i][2]];
f[k][x1][x2][x3]+=t;
}
printf("%d\n",f[2*N-1][N][N][N]);
return 0;
}
posted on 2009-07-28 16:46
xfstart07 阅读(335)
评论(0) 编辑 收藏 引用