棋盘型动态规划
int a[10][10],f[10][10][10][10];
int main(){
int n=read();
while(1){
int x=read(),y=read(),z=read();
if(!x&&!y&&!z)break;
a[x][y]=z;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++){
f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i][j-1][k-1][l],max(f[i-1][j][k][l-1],f[i][j-1][k][l-1])))+a[i][j]+a[k][l];
if(i==k&&j==l)f[i][j][k][l]-=a[i][j];
}
printf("%d\n",f[n][n][n][n]);
return 0;
}
跟上面的代码一样
int a[51][51],f[51][51][51][51];
int main(){
int m=read(),n=read();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
a[i][j]=read();
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
for(int l=1;l<=n;l++){
f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])))+a[i][j]+a[k][l];
if(i==k&&j==l)f[i][j][k][l]-=a[i][j];
}
printf("%d\n",f[m][n][m][n]);
return 0;
}
int a[55][55],f[105][55][55];
//因为第一维枚举的是步数,所以数组第一维要m+n
int main(){
int m=read(),n=read();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=m+n-1;i++)//枚举步数
for(int j=1;j<=m;j++)//枚举第一次DP的行
for(int k=1;k<=m;k++){//枚举第二次DP的行
if(i-j+1<1||i-k+1<1)continue;
//判断列是否合法,不合法就跳过
f[i][j][k]=max(f[i-1][j][k-1],max(f[i-1][j][k],max(f[i-1][j-1][k-1],f[i-1][j-1][k])))+a[j][i-j+1]+a[k][i-k+1];
if(j==k)f[i][j][k]-=a[j][i-j+1];
//判断是否经过了同一个点
}
printf("%d\n",f[m+n-1][m][m]);
return 0;
}
优质内容筛选与推荐>>