Solution Of P10972 I-Country

· · 题解

Solution

介绍一下蓝书上的 dp 做法。

注意到本题的阶段满足线性增长的特性，考虑线性 dp。

我们设状态 f_{i,j,l,r,x,y} 表示前 i 行选了 j 个格子，当前的第 i 行选了 l\sim r 个格子（包括第 l,r 个格子，若不选 l, r 均为零），左边界是否在扩张（即列号的单调性）记为 x，右边界是否在扩张记为 y。其中：

以下记：

S_{l, r} = \sum_{p = l} ^ {r} a_{i,p}

对 x,y 进行分讨，有以下转移。

f_{i, j, l, r, 1, 1} = S_{l, r} + \max_{l\le p \le r\le q} \left \{ \max_{0\le y\le 1} \left \{ f_{i - 1,j - (r - l + 1),p, q, 1, y} \right \} \right \} f_{i, j, l, r, 0, 0} = S_{l, r} + \max_{p\le l \le q\le r} \left \{ \max_{0\le x\le 1} \left \{ f_{i - 1,j - (r - l + 1),p, q, x, 0} \right \} \right \} f_{i, j, l, r, 1, 0} = S_{l, r} + \begin{cases} f_{i - 1, 0, 0, 0, 1, 0} &{\mathrm{if\ }} j = r - l + 1 > 0\\ \max_{l\le p \le q\le r} \left \{ f_{i - 1,j - (r - l + 1), p, q, 1, 0} \right \} &{\mathrm{if\ }} j > r - l + 1 > 0 \end{cases} f_{i, j, l, r, 0, 1} = S_{l, r} + \max_{p \le l \le r \le q} \left \{ \max_{0\le x \le 1} \left \{ \max_{0\le y \le 1} \left \{ f_{i - 1, j - (r - l + 1), p, q, x, y} \right \} \right \} \right \}

我们发现 n, m, k 很小，因此暴力转移即可。

本题还要求输出方案，我们记录每个阶段从上一个阶段的转移来源最后回溯输出即可。

本题转移不算难想，但是代码实现细节较多，具体见代码。

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define P(C) [C][C * C][C][C][2][2]
#define ft(tp, i, l, r) for (tp i = l; i <= r; i ++)
constexpr int N = 17;
int n, m, k, f P(N), a[N][N];
struct lst {
    int i, j, l, r, x, y;
    lst () : i(0), j(0), l(0), r(0), x(0), y(0) {};
    lst (int a, int b, int c, int d, int e, int f) : 
        i(a), j(b), l(c), r(d), x(e), y(f) {};
} pr P(N), ed;
void dp (int i, int j, int l, int r) {
    i64 sum = 0, len = r - l + 1, dt = 0;
    ft (int, p, l, r) sum += a[i][p];
    if (j == len) dt = f[i - 1][0][0][0][1][0];
    else ft (int, p, l, r) ft(int, q, p, r) if (f[i - 1][j - len][p][q][1][0] > dt) 
        dt = f[i - 1][j - len][p][q][1][0], pr[i][j][l][r][1][0] = lst(i - 1, j - len, p, q, 1,0);
    f[i][j][l][r][1][0] = sum + dt, dt = 0;
    ft(int, p, l, r) ft(int, q, r, m) ft(int, x, 0, 1) if (f[i - 1][j - len][p][q][1][x] > dt) 
        dt = f[i - 1][j - len][p][q][1][x], pr[i][j][l][r][1][1] = lst(i - 1, j - len, p, q, 1,x);
    f[i][j][l][r][1][1] = sum + dt, dt = 0;
    ft(int, p, 1, l) ft(int, q, l, r) ft(int, x, 0, 1) if (f[i - 1][j - len][p][q][x][0] > dt) 
        dt = f[i - 1][j - len][p][q][x][0], pr[i][j][l][r][0][0] = lst(i - 1, j - len, p, q, x,0);
    f[i][j][l][r][0][0] = sum + dt, dt = 0;
    ft(int, p, 1, l) ft(int, q, r, m) ft(int, x, 0, 1) ft(int, y, 0, 1) 
        if (f[i - 1][j - len][p][q][x][y] > dt) dt = f[i - 1][j - len][p][q][x][y], 
            pr[i][j][l][r][0][1] = lst(i - 1, j - len, p, q, x, y);
    f[i][j][l][r][0][1] = sum + dt, dt = 0;
}
void print (lst p) {
    if (p.j == 0) return ;
    print (pr[p.i][p.j][p.l][p.r][p.x][p.y]);
    ft(int, i, p.l, p.r) cout << p.i << ' ' << i << '\n';
}
i64 findans() {
    i64 ans = 0;
    ft(int, i, 1, n) ft(int, l, 1, m) ft(int, r, l, m) 
        ft(int, x, 0, 1) ft(int, y, 0, 1) if (ans < f[i][k][l][r][x][y]) 
            ans = f[i][k][l][r][x][y], ed = lst(i, k, l, r, x, y);
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m >> k;
    ft (int, i, 1, n) ft (int, j, 1, m) cin >> a[i][j];
    ft (int, i, 1, n) ft (int, j, 1, k) 
        ft (int, l, 1, m) ft (int, r, l, m) 
            if (j >= (r - l + 1)) dp(i, j, l, r);
    cout << "Oil : " << findans() << '\n';
    return print(ed), 0;
}