UVA 1427 Parade

單調隊列優化DP

參考原文

題意： F城由n+1個橫向路和m+1個豎向路組成。你的任務是從最南邊的路走到最北邊的路，使得走過的路上的高興值的和最大(高興值可能為負數)。同一段路最多隻能走一次，且不能從北往南走。另外，在每條橫向路上所花的時間不能超過k。1<=n<=100，1<=m<=10000，0<=k<=3000000。

解法： 很容易想到設dp[i][j]到第i行第j列那個點的最大值，設L[i][j]為從第i行的左邊走到i的最大值，R[i][j]為從第i行的右邊走到i的最大值，那麼有如下轉移：

dp[i][j] = max(L[i][j],R[i][j],dp[i+1][j])。注意邊界問題。

乍看之下問題貌似解決了。但是呢，如果對于每個點都要對他的同一行掃一遍來計算他的L和R，要m的時間，總共約n*m個點，複雜度O(n*m^2)，m範圍有1W，不逾時直播吃鍵盤- -！。

是以呢，考慮優化一下L和R的計算： L[i][j] = min(dp[i+1][k] + val[k~j])，0<=k<j。

如果happy值val處理成字首和的形式，會不會更快一點呢，那麼方程變為： L[i][j] = min(dp[i+1][k] + SumVal[0~j] - SumVal[0~k])。

光是字首和貌似效果還不夠好，那麼方程再變個型： L[i][j] = min(dp[i+1][k] - SumVal[0~k]) + SumVal[0~j]。

注意min括号裡的東西，dp[i+1][k]-SumVal[0~k]，這個式子，跟上上上面的方程的差別在于，他隻和k有關，k<j，那麼，集合{0~j} - 集合{0~j-1} = {j}，明顯的遞推關系！那麼在知道前向的結果的情況下，計算出這一項隻需要O(1)的時間！是以時間上可以優化到O(n*m)。

考慮對于橫向路的時間不能超過k這個限制的處理。我們需要的值是j節點左端不超過k時間範圍内的值，而每次遞推時增加的值在時間上都是穩定最小的，天然的時間遞減順序！

考慮插入時間為k的這個值時，他必定是在最右端的，對于他左端比他小的值，可以直接忽略了(因為更小的範圍，值還比你大，我要你做什麼)，而左端比他大的值，若時間不超過範圍，則不能删去，因為可能會用到。這樣，就構成了一個由左到右，在時間上遞減，在happy值上也遞減的序列，要維護這樣一個序列，要支援兩端删除，右端插入，顯然是雙端隊列這個資料結構了。每次要取最大值時從最左端取值，時間O(1)，每個值最多進隊一次，出隊一次，處理一行的時間為O(m)，so nice！

總結： 單調隊列優化的DP具有這樣的性質： 有dp[i] = min(h[i]) +　g[i],他的取最值部分h[i]可以被劃分成與i值無關的，可遞推的式子，這樣的方程用單調隊列能夠将複雜度降一個幂次。

對于這道題，在POJ上貌似用C++光是讀入就已經逾時了。是以用G++和快速讀入優化了一下，一不小心刷到第一了- -

/* **********************************************
Author      : Nero
Created Time: 2013-8-30 15:17:38
Problem id  : UVA 1427
Problem Name: Parade
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(int)(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))

const int INF = 0x3f3f3f3f;                                                                                                                                   
int mat[110][10100];
int path[110][10100];
int n,m,K;
struct Q {
    int val,time;
}q[10100];
int qf,qe;
int dp[10100];
int temp[10100];

inline int GetInt() {
    char c;
    do {
        c = getchar();
    }while(!isdigit(c) && c != '-');
    int ret = 0;
    int sigma = 1;
    if(c == '-') sigma = -1;
    else ret = c - '0';
    while(isdigit(c = getchar())) ret = ret * 10 + c - '0';
    return ret*sigma;
}

int main() {
    while(~scanf("%d%d%d", &n, &m, &K), n || m || K) {
        clr(dp,0);
        for(int i = 0; i <= n; i ++) path[i][0] = path[i][m+1] = 0;
        for(int i = 0; i <= n; i ++) mat[i][0] = mat[i][m+1] = 0;
        for(int i = 0; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                mat[i][j] = GetInt();
                mat[i][j] += mat[i][j-1];
            }
        }
        for(int i = 0; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                path[i][j] = GetInt();
                path[i][j] += path[i][j-1];
            }
        }
        for(int i = n; i >= 0; i --) {
            for(int j = 0; j <= m; j ++) temp[j] = dp[j];
            qf = 0;
            qe = -1;
            for(int j = 1; j <= m; j ++) {
                int tv = temp[j-1] - mat[i][j-1];
                while(qf <= qe && q[qe].val <= tv) qe --;
                q[++qe].val = tv;
                q[qe].time = path[i][j-1];
                while(qf <= qe && path[i][j]-q[qf].time > K) qf ++;
                if(qf <= qe) dp[j] = max(dp[j], q[qf].val+mat[i][j]);
            }

            qf = 0;
            qe = -1;
            for(int j = m-1 ; j >= 0; j --) {
                int tv = temp[j+1] + mat[i][j+1];
                while(qf <= qe && q[qe].val <= tv) qe --;
                q[++qe].val = tv;
                q[qe].time = path[i][j+1];
                while(qf <= qe && q[qf].time - path[i][j] > K) qf ++;
                if(qf <= qe) dp[j] = max(dp[j], q[qf].val-mat[i][j]);
            }
        }
        
        int maxn = -(~0u>>1);
        for(int i = 0; i <= m; i ++) {
            maxn = max(maxn, dp[i]);
        }
        printf("%d\n", maxn);
    }
    return 0;
}