UVa 1427. Parade

Description

一個城市有n+1個橫向路和m+1個縱向路,一個國王從最北邊的進入,然後沿某種路線從最南邊出去,每小段橫向路都有一個高興值,但國王不會在某條橫向路待超過k分鐘,問國王可以得到的最大的高興值是多少?

Input Format

輸入包含多筆測資,第一行為$n\ m\ k$三整數,若$n=m=k=0$則程式結束。
接下來有$n+1$行,代表從北到南的東西向道路。 每行有$m$個數字,代表此道路m個區域從西到東的高興值。 再來有$n+1$行,也代表從北到南的東西向道路。 每行有$m$個數字,代表此道路m個區域從西到東的長度。

Output Format

每筆測資輸出一行,輸出最大的高興值,答案保證小於$2^{32}$。

Sample Input

2 3 2
7 8 1
4 5 6
1 2 3
1 1 1
1 1 1
1 1 1
0 0 0
# Sample Output
27
本測資示意圖如下: ![](1.png) UVa - [1427](https://uva.onlinejudge.org/external/14/1427.pdf)

Solution

這題很明顯的是DP。但是如果用一般的DP寫,時間複雜度是$O(nm^2)$,會導致TLE,所以需要用優化將其複雜度壓下一個維度。
由於這是我第一次寫有關單調隊列的題解,所以在推導過程中可能不會寫得很好。

令$dp[i][j]$為第i行時j點的最大幸福度。則可以轉移式可以寫成如下:
$dp[i][j] = max(dp[i][j], dp[i-1][k]+\text{happy_sum}[k\text{}j]) 且 \text{length_sum}[k\text{}j] \le K$
為了方便計算,令
$happy[i]=從0\text{}i的高興值總和$
$len[i]=從0\text{
}i道路長度總和$
則可以寫成:
$dp[i][j] = max(dp[i][j],\text{ }dp[i-1][k] + happy[j] - happy[k]) 且 len[j] - len[k] \le K$
移項得:
$(dp[i - 1][k] - happy[k]) + happy[j]$
很明顯可以看出可以利用deque,維護$(dp[i - 1][k] - happy[k])$的遞減佇列,並在當最前項$len[j] - len[k] > K$時pop掉,以確保最前項在滿足條件下為最大值。

以上推倒過程只有討論到「左到右」的,實際上還要考慮「右到左」的移動。
時間複雜度:$O(nm)$

Code

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
/*************************************************************************
> File Name: 01427 - Parade.cpp
> Author: Samuel
> Mail: [email protected]
> Created Time: Tue Dec 11 09:21:54 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll dp[2][10010];
ll happy[110][10010];
ll len[110][10010], k;
int dq[10010], l, r;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> n >> m >> k && (n || m || k)) {
n++;
for (int i = n; i; i--)
for (int j = 1; j <= m; j++) {
cin >> happy[i][j];
happy[i][j] += happy[i][j - 1];
}
for (int i = n; i; i--)
for (int j = 1; j <= m; j++) {
cin >> len[i][j];
len[i][j] += len[i][j - 1];
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
int now = i & 1;
int prev = !now;
l = r = 0;
for (int j = 0; j <= m; j++) {
while (l != r && len[i][j] - len[i][dq[l]] > k)
l++;
while (l != r && dp[prev][j] - happy[i][j] >= dp[prev][dq[r - 1]] - happy[i][dq[r - 1]])
r--;
dq[r++] = j;
dp[now][j] = dp[prev][dq[l]] - happy[i][dq[l]] + happy[i][j];
}
l = r = 0;
for (int j = m; j >= 0; j--) {
while (l != r && len[i][dq[l]] - len[i][j] > k)
l++;
while (l != r && dp[prev][j] + happy[i][j] >= dp[prev][dq[r - 1]] + happy[i][dq[r - 1]])
r--;
dq[r++] = j;
dp[now][j] = max(dp[now][j], dp[prev][dq[l]] + happy[i][dq[l]] - happy[i][j]);
}
}
ll ans = 0;
for (int i = 0; i <= m; i++)
ans = max(ans, dp[n & 1][i]);
cout << ans << '\n';
}
return 0;
}