/ zzf / 讨论 / 题解 /

传纸条

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[51][51],f[200][51][51];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        scanf("%d",&a[i][j]);
    for(int i=2;i<=m+n-1;i++)
      for(int j=1;j<=min(i,m);j++)
        for(int k=1;k<=min(i,m);k++){
          f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]);
          f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]);
          f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]);
          f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
          if(k==j) f[i][j][k]+=a[j][i-j+1];
          if(k!=j) f[i][j][k]+=a[j][i-j+1]+a[k][i-k+1];
        } 
    printf("%d",f[m+n-1][m][m]);
}

1 条评论

  • 1