UVa 1427. Parade

2018-12-11

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

Sample Output

本測資示意圖如下：
UVa - 1427

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\sim j]), \ \text{length-sum}[k\sim j] \le K$
為了方便計算，令
$happy[i]=從0\sim i的高興值總和$
$len[i]=從0\sim i道路長度總和$
則可以寫成：
$dp[i][j] = max(dp[i][j],\ 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

/*************************************************************************
  > File Name: 01427 - Parade.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > 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;
}