solution
注意到。
考虑时如何做。
令表示前i个位置选出了j段的最大价值。转移就是
同样的方法我们可以类比出时的做法。
令表示第1列选到了第i个数,第二列选到了第j个数,总共选了k个矩阵的最大价值。
转移就枚举一下最后放的一个矩阵,如果最后一个矩阵放在了第1列,那就从转移过来。如果最后一个矩阵放在了第2列,那就从转移过来。如果,就可以在最后放一个的矩阵,那就从转移过来
code
/* * @Author: wxyww * @Date: 2020-06-05 21:24:15 * @Last Modified time: 2020-06-05 21:59:50 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 110; #define int ll ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int a[N][3],f[N][N][11]; signed main() { int n = read(),m = read(),K = read(); memset(a,-0x3f,sizeof(a)); a[0][1] = a[0][2] = 0; for(int i = 1;i <= n;++i) { for(int j = 1;j <= m;++j) { a[i][j] = a[i - 1][j] + read(); } } memset(f,-0x3f,sizeof(f)); f[0][0][0] = 0; for(int i = 0;i <= n;++i) { for(int j = 0;j <= n;++j) { for(int k = 0;k <= K;++k) { if(i) f[i][j][k] = max(f[i][j][k],f[i - 1][j][k]); if(j) f[i][j][k] = max(f[i][j][k],f[i][j - 1][k]); if(!k) continue; for(int t = 0;t < j;++t) f[i][j][k] = max(f[i][j][k],f[i][t][k - 1] + a[j][2] - a[t][2]); for(int t = 0;t < i;++t) f[i][j][k] = max(f[i][j][k],f[t][j][k - 1] + a[i][1] - a[t][1]); if(i != j) continue; for(int t = 0;t < i;++t) f[i][j][k] = max(f[i][j][k],f[t][t][k - 1] + a[i][1] - a[t][1] + a[i][2] - a[t][2]); } } } cout<<f[n][n][K]<<endl; return 0; }