P3444 [POI2006]ORK-Ploughing

Alex_Wei · 2021-12-13 16:33:44 · 题解

*P3444 [POI2006]ORK-Ploughing

POI 合集。

有趣的思维题。

考虑到最后必然是行或者列被删完，所以我们不妨设行被删完。

接下来，考虑固定左右各删去多少列，即设 f_{l,r} 表示还剩 l\sim r 这些列时，尽量删行之后剩下来的行数的区间 [p_{l,r},q_{l,r}]（因为我们要让行尽快被删完）。

区间 [p,q] 是唯一的，反证法可证：假设存在另一个区间 [p',q']，不妨设 q'<q，那么可以删到 [p,q']，与 “尽量删” 的定义矛盾。同理，若 p<p'，我们也可以删到 [p,q]。\square

考虑如何求出 f_{l,r}。显然，它要从 f_{l-1,r} 和 f_{l,r+1} 转移过来。如果 f_{l-1,r} 最左边一列能删掉，即 k\geq \sum_{\\i=p_{l-1,r}}^{q_{l-1,r}}t_{i,j}，那么 f_{l,r} 继承 f_{l-1,r}。同理，若 f_{l,r+1} 最右边一列能删掉，f_{l,r} 也可以继承 f_{l,r+1}。任意继承不会影响复杂度：均摊证明时间复杂度是 \mathcal{O}(nm) 的。

同理，假设列被删完再做一遍上述算法即可得到正确答案。

const int N = 2e3 + 5;
int n, m, k, ans = N << 1, row[N][N], c[N][N];
pii f[N][N];
int main(){
    cin >> k >> m >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            c[i][j] = c[i - 1][j] + (row[i][j] = read()), row[i][j] += row[i][j - 1];
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            f[i][j] = {0, m}; f[1][n] = {1, m};
    for(int len = n; len; len--)
        for(int l = 1, r = len; r <= n; l++, r++) {
            int p = f[l][r].fi, q = f[l][r].se;
            if(!p) continue;
            while(p <= q && c[r][p] - c[l - 1][p] <= k) p++;
            while(p <= q && c[r][q] - c[l - 1][q] <= k) q--;
            if(p > q) cmin(ans, n - len + m);
            if(row[l][q] - row[l][p - 1] <= k) f[l + 1][r] = {p, q};
            if(row[r][q] - row[r][p - 1] <= k) f[l][r - 1] = {p, q};
        }
    for(int i = 1; i <= m; i++)
        for(int j = i; j <= m; j++)
            f[i][j] = {0, n}; f[1][m] = {1, n};
    for(int len = m; len; len--)
        for(int l = 1, r = len; r <= m; l++, r++) {
            int p = f[l][r].fi, q = f[l][r].se;
            if(!p) continue;
            while(p <= q && row[p][r] - row[p][l - 1] <= k) p++;
            while(p <= q && row[q][r] - row[q][l - 1] <= k) q--;
            if(p > q) cmin(ans, n + m - len);
            if(c[q][l] - c[p - 1][l] <= k) f[l + 1][r] = {p, q};
            if(c[q][r] - c[p - 1][r] <= k) f[l][r - 1] = {p, q};
        }
    cout << ans << endl;
    return 0;
}