真 · 码农题
(dp) $O(n^7)$
考虑到一个凸多边形一定是连续的多行组成。可以考虑每行选哪几个格子。
设 $0$ 为单调伸长, $1$ 为单调伸短。
设 $f[i][j][l][r][x\ (0 / 1) ][y\ (0 / 1)]$ 为第 $i$ 行,已经选出$j$个格子,第$i$行选择了$[l, r]$ 区间的最大值。左右端点$x, y$分别为 单调伸长 / 单调伸短 的最大权值。
状态转移:
-
若 $x = 0, y = 0$,则 $f[i][j][l][r][x][y] = max(f[i - 1][j - (r - l + 1)][l’][r’][0][0]) + cost(i, l, r)$ ,其中$l <= l’ <= r’ <= r, j >= r - l + 1$。
-
若 $x = 0, y = 1$, 则 $f[i][j][l][r][x][y] = max(f[i - 1][j - (r - l + 1)][l’][r’][0][0 / 1]) + cost(i, l, r)$,其中$l <= l’ <= r <= r’, j >= r - l + 1$。
-
若 $x = 1, y = 0$, 则 $f[i][j][l][r][x][y] = max(f[i - 1][j - (r - l + 1)][l’][r’][0 / 1][0]) + cost(i, l, r)$,其中$l’ <= l <= r’ <= r, j >= r - l + 1$ 。
- 若 $x = 1, y = 1$, 则 $f[i][j][l][r][x][y] = max(f[i - 1][j - (r - l + 1)][l’][r’][0 / 1][0 / 1]) + cost(i, l, r)$,其中$l’ <= l <= r <= r’, j >= r - l + 1$ 。
初始状态: $f[i][0][l][r][0][0] = 0 (0 <= i <= n, 1 <= l <= r <= m)$,其余为负无穷。
目标:$max\{f[i][k][l][r][0 / 1][0 / 1]\} (1 <= i <= n)$
输出方案只需通过状态转移延展即可。$cost(i, l, r)$ 用前缀和计算
时间复杂度$O(n ^ 7)$
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 16;
struct S{
int i, j, l, r, x, y;
}pre[N][N * N][N][N][2][2], t;
int n, m, k, a[N][N], f[N][N * N][N][N][2][2];
int ans = 0;
int inline cost(int i, int l, int r){
return a[i][r] - a[i][l - 1];
}
void print(S x){
if(x.j == 0) return;
print(pre[x.i][x.j][x.l][x.r][x.x][x.y]);
for(int i = x.l; i <= x.r; i++)
printf("%d %d\n", x.i, i);
}
int main(){
memset(f, 0xcf, sizeof f);
scanf("%d%d%d", &n, &m, &k);
for(int r = 0; r <= n; r++) {
for(int i = 1; i <= m; i++){
for(int j = i; j <= m; j++)
f[r][0][i][j][0][0] = 0;
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &a[i][j]), a[i][j] += a[i][j - 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
for(int l = 1; l <= m; l++){
for(int r = l; r <= m; r++){
if(j < r - l + 1) continue;
//x = 0, y = 0;
for(int l1 = l; l1 <= r; l1++){
for(int r1 = l1; r1 <= r; r1++){
int &v = f[i][j][l][r][0][0], val = f[i - 1][j - (r - l + 1)][l1][r1][0][0] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][0][0] = (S){i - 1, j - (r - l + 1), l1, r1, 0, 0};
}
}
}
//x = 0, y = 1;
for(int l1 = l; l1 <= r; l1++){
for(int r1 = r; r1 <= m; r1++){
for(int y1 = 0; y1 < 2; y1++) {
int &v = f[i][j][l][r][0][1], val = f[i - 1][j - (r - l + 1)][l1][r1][0][y1] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][0][1] = (S){i - 1, j - (r - l + 1), l1, r1, 0, y1};
}
}
}
}
// x = 1, y = 0;
for(int l1 = 1; l1 <= l; l1++){
for(int r1 = l; r1 <= r; r1++){
for(int x1 = 0; x1 < 2; x1++) {
int &v = f[i][j][l][r][1][0], val = f[i - 1][j - (r - l + 1)][l1][r1][x1][0] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][1][0] = (S){i - 1, j - (r - l + 1), l1, r1, x1, 0};
}
}
}
}
// x = 1, y = 1;
for(int l1 = 1; l1 <= l; l1++){
for(int r1 = r; r1 <= m; r1++){
for(int x1 = 0; x1 < 2; x1++) {
for(int y1 = 0; y1 < 2; y1++) {
int &v = f[i][j][l][r][1][1], val = f[i - 1][j - (r - l + 1)][l1][r1][x1][y1] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][1][1] = (S){i - 1, j - (r - l + 1), l1, r1, x1, y1};
}
}
}
}
}
if(j == k){
for(int x = 0; x < 2; x++) {
for(int y = 0; y < 2; y++) {
if(ans < f[i][j][l][r][x][y]) {
ans = f[i][j][l][r][x][y], t = (S){i, j, l, r, x, y};
}
}
}
}
}
}
}
}
printf("Oil : %d\n", ans);
print(t);
return 0;
}
Remake的代码居然跟我有异曲同工之妙orz
想问一下大佬,怎么确定 r1 - l1 + 1不会超过 j - (r - l + 1)呢
这个状态是非法会被赋成负无穷,不影响
谢谢大佬
大佬最后不应该求f[i][j][l][r][0][1] 这个末态才是凸联通体吗,为何要枚举x y啊
在任何状态下我们求的图行都是一个凸多边形,你画一下图就知道了,因为我们规定左右只有一个峰值。
啊哈哈哈哈
QWQ