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