标签：ref   tin   line   space   cos   cstring   初始   sizeof   str   

题目链接

设 \(0\) 为单调伸长， \(1\) 为单调伸短。

设 \(f[i][j][l][r][x(0 / 1)][y (0 / 1)]\) 为第 \(i\) 行，已经选出\(j\)个格子，第\(i\)行选择了\([l, r]\) 区间的最大值。左右端点\(x, y\)分别为 单调伸长 / 单调伸短 的最大权值。

状态转移：

1. 若 \(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 = r - l + 1\)。

2. 若 \(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 = r - l + 1\)。

3. 若 \(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' = r - l + 1\) 。

4. 若 \(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' = r - l + 1\) 。

初始状态： \(f[i][0][l][r][0][0] = 0 (0 ，其余为负无穷。

目标：\(max\{f[i][k][l][r][0 / 1][0 / 1]\} (1

输出方案只需通过状态转移延展即可。\(cost(i, l, r)\) 用前缀和计算?

时间复杂度\(O(n ^ 7)\)

C++ 代码

#include 
#include 
#include 
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 

AcWing 276. I-区域

标签：ref   tin   line   space   cos   cstring   初始   sizeof   str   

原文地址：https://www.cnblogs.com/dmoransky/p/11442169.html