AcWing 2607. 最大子矩阵
原题链接
困难
作者:
T-God韩枫
,
2022-04-02 10:54:16
,
所有人可见
,
阅读 279
每个状态分类讨论
#include <bits/stdc++.h>
#define int long long
int _ = 0, Case = 1;
using namespace std;
#define all(v) begin(v),end(v)
#define nline '\n'
const int N = 110;
int a[N][3];
int f[N][20][5];
void solve(int Case) {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
memset(f, 0xcf, sizeof f);
if (m == 1) {
f[0][0][0] = 0;
//f[0][0][1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
f[i][j][0] = max(f[i - 1][j][1], f[i - 1][j][0]);
f[i][j][1]=f[i-1][j][1]+a[i][1];
if (j)
f[i][j][1] = max(max(f[i - 1][j - 1][0], f[i - 1][j - 1][1])+a[i][1],f[i][j][1]);
}
}
cout << max(f[n][k][1], f[n][k][0]) << nline;
}
else {
f[0][0][0]=0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
for (int t = 0; t <= 4; t++) {
f[i][j][0] = max(f[i][j][0], f[i - 1][j][t]);
}
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][4]) + a[i][1];
for (int t = 0; t <= 4; t++) {
if (j)
f[i][j][1] = max(f[i - 1][j - 1][t] + a[i][1], f[i][j][1]);
}
f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j][4]) + a[i][2];
for (int t = 0; t <= 4; t++) {
if (j)
f[i][j][2] = max(f[i - 1][j - 1][t] + a[i][2], f[i][j][2]);
}
f[i][j][3] = max(f[i - 1][j][3] + a[i][1] + a[i][2], f[i][j][3]);
for (int t = 0; t <= 4; t++) {
if (j)
f[i][j][3] = max(f[i - 1][j - 1][t] + a[i][2] + a[i][1], f[i][j][3]);
}
f[i][j][4] = max(f[i - 1][j][4] + a[i][1] + a[i][2], f[i][j][4]);
if (j)
f[i][j][4] = max(max(f[i - 1][j - 1][1], f[i - 1][j - 1][2]) + a[i][1] + a[i][2], f[i][j][4]);
for (int t = 0; t <= 4; t++) {
if (j >= 2)
f[i][j][4] = max(f[i - 1][j - 2][t] + a[i][2] + a[i][1], f[i][j][4]);
}
}
}
int res = 0;
for (int i = 0; i <= 4; i++) res = max(f[n][k][i], res);
cout << res << nline;
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
// cin >> _; for (Case = 1; Case <= _; Case++)
solve(Case);
return 0;
}
666