uva1427 單調隊列優化dp

每條東西走向路有（高興值，時間）二維參量，要從最南邊走到最北邊，滿足：1）每條道路僅走一次2）每行道路所經過的總時間不超過k，求最大高興值的和3）不能從北向南走

狀态：f[i][j]:到達第i行第j個頂點（從左起）最大高興值。

最短/長路問題：狀态常設為以某點為起點/終點的最優值

求數組f。到達（i，j）可以從左、右、下三個方向。設輔助數組L[i][j]從左邊到達（i，j）的最大高興值，R[i][j]:從右邊到達（i，j）的最大高興值，則f[i][j]=max(f[i+1][j],L[i][j],R[i][j])

求輔助數組L與R。

L[i][j]=max{f[i+1][k]+sumvalue[i][j]-sumvalue[i][k],1<=k<=j&&sumtime[i][j]-sumtime[i][k]<=K}

       =max{funL(i,k),1<=k<=j&&sumtime[i][j]-sumtime[i][k]<=K}+sumvalue[i][j]

其中funL(i,k)=f[i+1][k]-sumtime[i][k]

R[i][j]=max{f[i+1][k]+sumvalue[i][k]-sumvalue[i][j],j<=k<=m+1&&sumtime[i][k]-sumtime[i][j]<=K}

        =max{funR(i,k),j<=k<=m+1&&sumtime[i][k]-sumtime[i][j]<=K}-sumvalue[i][j]

其中funR(i,k)=f[i+1][k]+sumvalue[i][k]

對于L和R數組的求解可以用單調隊列進行優化，原理同la3983撿垃圾的機器人一題

單減隊列維護滿足區間條件的最大值，置于隊首（top）

單增隊列維護滿足區間條件的最小值，置于隊首（top）

單調隊列的三個步驟：

1.當隊首（top）元素不滿足區間條件時，從隊首（top）删去

2.取出目前維護的top值進行操作

3.從隊尾（tail）依次删除比要加入的元素大（單增隊列）/小（單減隊列）的元素，最後将新元素加入單調隊列

注：輸入需要用字元串進行加速，否則會逾時！

#include<stdio.h>
 #include<string.h>
 #include<iostream>
 #define mem(a,b) memset(a,b,sizeof(a))
 using namespace std;

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

 const int maxrow=200+10;
 const int maxcol=20000+10;
 const int INF = 0x3f3f3f3f;

 int n,m,K;
 int sumvalue[maxrow][maxcol],sumtime[maxrow][maxcol];
 int f[maxrow][maxcol];//第i行走到第j個頂點的最大價值
 int L[maxrow][maxcol],R[maxrow][maxcol];
 int que[maxcol];

 void prepare(){//計算第i行的走到第j個頂點的價值和與時間和
    int value,hour;
    //sumvalue[i][1]和sumtime[i][1]均為0
    for(int i=1;i<=n+1;i++){
        sumvalue[i][1]=0;
        for(int j=2;j<=m+1;j++){
            value=GetInt();
            sumvalue[i][j]=sumvalue[i][j-1]+value;
        }
    }
    for(int i=1;i<=n+1;i++){
        sumtime[i][1]=0;
        for(int j=2;j<=m+1;j++){
            hour=GetInt();
            sumtime[i][j]=sumtime[i][j-1]+hour;
        }
    }
 }

 int funL(int i,int j){//計算L[i][j]中的fun函數
     return f[i+1][j]-sumvalue[i][j];
}

int funR(int i,int j){//計算R[i][j]中的fun函數
    return f[i+1][j]+sumvalue[i][j];
}

 void fun(){//計算f[i][j]
    mem(f,0),mem(L,0),mem(R,0);
    int top,tail;
    for(int i=n+1;i>=1;i--){//第i行
        L[i][1]=f[i+1][1];
        top=tail=1,que[1]=1;
        for(int j=2;j<=m+1;j++){//第j列L數組
            while(top<=tail&&sumtime[i][j]-sumtime[i][que[top]]>K) top++;
            L[i][j]=funL(i,que[top])+sumvalue[i][j];
            //printf("L:%d %d %d\n",i,j,L[i][j]);
            while(top<=tail&&funL(i,que[tail])<=funL(i,j)) tail--;
            que[++tail]=j;
        }
        R[i][m+1]=f[i+1][m+1];
        top=tail=1,que[1]=m+1;
        for(int j=m;j>=1;j--){//第j列R數組
            while(top<=tail&&sumtime[i][que[top]]-sumtime[i][j]>K) top++;
            R[i][j]=funR(i,que[top])-sumvalue[i][j];
           // printf("R:%d %d %d\n",i,j,R[i][j]);
            while(top<=tail&&funR(i,que[tail])<=funR(i,j)) tail--;
            que[++tail]=j;
        }
        for(int j=1;j<=m+1;j++){//第j列f數組
            f[i][j]=max(f[i+1][j],max(L[i][j],R[i][j]));
        }
    }
 }

 int main(){
    //freopen("a.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&K)!=EOF,n||m||K){
       prepare();
       fun();
       int ans=-INF;
       for(int j=1;j<=m+1;j++) ans=max(ans,f[1][j]);
       printf("%d\n",ans);
    }
 }