【题解】HackerRank - Cut a Strip

Posted on In Disqus:

题目

https://www.hackerrank.com/contests/w36/challenges/cut-a-strip

题意

给一个矩阵，可以将其中大小 \(1\times x ~(1\leq x\le k)\) （纵横均可）变成 0，求操作后最大子矩阵和。

题解

  • 如果没有修改，那么就是枚举两行，预处理列的前缀和后就转化为经典的最大子段和了。
  • 现在这个最大子段和问题，多出了一次修改，用 dp 记录一下修改有没有用过即可。
  • 问题在于要在一列的一个区间中贪心地去掉长度不超过 \(k\) 的子段，使得剩下的和最大（也就是子段和最小）。这个过程在枚举行的下界时用单调队列维护一下，求出最小子段和。
  • 因为去掉的不一定是列的一部分，还可能是行的一部分，所以要转置后再计算一次。
  • 由于操作是必须进行的，矩阵中所有元素都为正数需要特判，强行去掉矩阵中的最小元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 380 + 10;
int a[maxn][maxn], n, m, k, ps[maxn][maxn], b[maxn][maxn];
deque<int> q[maxn];
int ans, v[maxn], vv[maxn], f[maxn], g[maxn], all, Min = 1E9;

int add(int idx, int ps[maxn], deque<int>& q) {
    while (!q.empty() && ps[q.back()] < ps[idx]) q.pop_back();
    q.push_back(idx);
    if (idx - q.front() > k) q.pop_front();
    return ps[idx] - ps[q.front()];
}

void go(int n, int m, int a[maxn][maxn]) {
    FOR (i, 1, n + 1)
        FOR (j, 1, m + 1)
            ps[j][i] = ps[j][i - 1] + a[i][j];

    FOR (l, 1, n + 1) {
        FOR (j, 1, m + 1) { q[j].clear(); q[j].push_back(l - 1); }
        memset(v, 0, sizeof v);
        FOR (r, l, n + 1) {
            FOR (j, 1, m + 1) {
                vv[j] = ps[j][r] - ps[j][l - 1];
                v[j] = min(v[j], add(r, ps[j], q[j]));
            }
            int f = 0, g = 0;
            FOR (i, 1, m + 1) {
                g = max(max(f, 0) + vv[i] - v[i], max(g, 0) + vv[i]);
                f = max(f, 0) + vv[i];
                ans = max(ans, g);
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    FOR (i, 1, n + 1)
        FOR (j, 1, m + 1) {
            int t;
            scanf("%d", &t);
            a[i][j] = b[j][i] = t; all += t; Min = min(Min, t);
        }
    if (Min >= 0) { cout << all - Min << endl; return 0; }
    go(n, m, a);
    go(m, n, b);
    cout << ans << endl;
}