0%

【题解】HackerRank - Cut a Strip

题目

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;
}