Uva(1427)(Parade)

链接：https://vjudge.net/problem/UVA-1427
思路：状态不难想，每上一层的一个点的最大值就等于下一层左右时间范围内各点过来的最大值，但是这样的话最坏情况有nm^2个状态需要枚举，肯定超时，肯定需要优化，而且优化的地方肯定是在枚举各点过来的地方，我们希望这个时间能在常数时间内完成，不妨设从左边过来，那么 dp[i-1][j] = dp[i][k]+sum[k][j]，继续变形一下就等于dp[i-1][j] = dp[i][k]+sum[j]-sum[k]，我们发现只跟最大值dp[i][k]-sum[k]有关，那么我们就可以把这一段用一个单调队列来维护，每次取队首元素就是最大值，当位置往右遍历时单调队列跟着变化，即可将复杂度降为O(nm)，这只是左边，右边类似，倒过来遍历一遍即可，只是要维护的变成了dp[i][k]+sum[k]，然后比较两种取最大值即可。注意学习单调队列的写法，这里单调队列最好是维护数组的下标，这样方便移动，不用再另外记录。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
const int maxn = 110;
const int maxm = 10010;
int t[maxn][maxm];
int dp[maxm];
int sum[maxn][maxm];
int q[maxm],d[maxm];

int main(){
    while(scanf("%d%d%d",&n,&m,&k)&&n||m||k){
        memset(sum,0,sizeof(sum));
        memset(t,0,sizeof(t));
        for(int i=0;i<=m;i++)dp[i] = 0;
        int tt;
        for(int i=1;i<=n+1;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&tt);
                sum[i][j] = sum[i][j-1] + tt;
            }
        }    
        for(int i=1;i<=n+1;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&tt);
                t[i][j] = t[i][j-1] + tt;
            }
        }    
        for(int i=n+1;i>=1;i--){
            for(int j=0;j<=m;j++){
                d[j] = dp[j];
            }
            int front = 0,rear = -1;
            for(int j=0;j<=m;j++){
                tt = d[j] - sum[i][j];
                while(front<=rear&&tt>=d[q[rear]]-sum[i][q[rear]])rear--;
                q[++rear] = j;
                while(front<=rear&&t[i][j]-t[i][q[front]]>k)front++;
                tt = d[q[front]] - sum[i][q[front]] + sum[i][j];
                dp[j] = max(dp[j],tt);
            }
            front = 0;
            rear = -1;
            for(int j=m;j>=0;j--){
                tt = d[j] + sum[i][j];
                while(front<=rear&&tt>=d[q[rear]]+sum[i][q[rear]])rear--;
                q[++rear] = j;
                while(front<=rear&&t[i][q[front]]-t[i][j]>k)front++;
                tt = d[q[front]] + sum[i][q[front]] - sum[i][j];
                dp[j] = max(dp[j],tt);
            }
        }
        int ans = -1e9;
        for(int i=0;i<=m;i++)
        ans = max(ans,dp[i]);
        printf("%d\n",ans);
    }
        return 0;
}