UVA live-4327(スライドキュー最適化dp)

方法は問題と同じで、
各層についてd[i][j]の最適解はmax(d[I−1][j],L(I,j),R(i,j))である.
ここで、L(i,j)は、i,jから左へいくつかの位置を歩く最適解を表す.
ここではL(I,J)の求め方のみについて議論する.
L(i,j) = max( f[i-1][k] -sum[k] ) +sum[j];(ただしdist(i,k)<=最大走行長)記func(i,j)はmax(f[i-1][j]-sum[j])である各層に対してスライドキューでメンテナンスするだけで、o(n)毎にL(i)を求めることができる.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long LL;
const int maxn = 105;
const int maxm = 10100;
LL f[maxn][maxm],t[maxn][maxm],L[maxm],R[maxm],n,m,c,d[maxn][maxm];
deque<int> Q;
int Lfunc(int j,int i){
  return d[i-1][j] - f[i][j];
}
int Rfunc(int j,int i){
  return d[i-1][j] + f[i][j];
}
int main()
{
    while(scanf("%lld %lld %lld",&n,&m,&c)==3&&n){
        for(int i=1;i<=n+1;i++)
          for(int j=0;j<=m;j++){
            if(!j) f[i][j] = 0;
            else{
                scanf("%lld",&f[i][j]);
                f[i][j]+=f[i][j-1];
            }
        }
        for(int i=1;i<=n+1;i++)
          for(int j=1;j<=m;j++){
            if(!j) t[i][j] = 0;
            else{
                scanf("%lld",&t[i][j]);
                t[i][j]+=t[i][j-1];
            }
        }
        for(int i=0;i<=m;i++) d[0][i] = 0;
        for(int i=1;i<=n+1;i++){
            L[0] = d[i-1][0];
            Q.clear(); Q.push_back(0);
            for(int j=1;j<=m;j++){
                while(!Q.empty()&&t[i][j]-t[i][Q.front()]>c){
                 Q.pop_front();
                }
                L[j] = d[i-1][j];
                if(!Q.empty()) L[j] =max(L[j],Lfunc(Q.front(),i)+f[i][j]);
                while(!Q.empty()&&Lfunc(Q.back(),i)<=Lfunc(j,i)) Q.pop_back();
                Q.push_back(j);
            }
            R[0] = d[i-1][m];
            Q.clear(); Q.push_back(m);
            for(int j=m-1;j>=0;j--){
                while(!Q.empty()&&t[i][Q.front()]-t[i][j]>c) Q.pop_front();
                R[j] = d[i-1][j];
                if(!Q.empty()) R[j] = Rfunc(Q.front(),i)-f[i][j];
                while(!Q.empty()&&Rfunc(Q.back(),i)<=Rfunc(j,i)) Q.pop_back();
                Q.push_back(j);
            }
            for(int j=0;j<=m;j++)
               d[i][j] = max(L[j],R[j]);
        }
        LL res;
        for(int i=0;i<=m;i++){
           if(!i) res=d[n+1][i];
           else res = max(d[n+1][i],res);
        }
        printf("%lld
",res);
    }
    return 0;
}