传纸条(动态规划)
作者:
amagi
,
2023-06-04 18:57:34
,
所有人可见
,
阅读 158
#include <iostream>
using namespace std;
const int N = 100;
int m,n;
int x[N][N];
int f[N * N][N][N];
int main(){
cin >> m >> n;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++) cin >> x[i][j];
}
for(int k = 2; k <= m + n; k ++){
for(int x1 = max(1,k - n); x1 <= min(k - 1,m); x1 ++){
for(int x2 = max(1,k - n); x2 <= min(k - 1,m);x2 ++){
int t = x[x1][k - x1];
if(x1 != x2) t += x[x2][k - x2];
for(int a = 0; a <= 1; a ++)
for(int b = 0; b <= 1; b ++)
f[k][x1][x2] = max(f[k][x1][x2],f[k - 1][x1 - a][x2 - b] + t);
}
}
}
cout << f[m + n][m][m] << endl;
}