hdu 4374 单调队列优化DP

http://acm.hdu.edu.cn/showproblem.php?pid=4374

题意：很简单，不废话了- -

在这道题中单调队列的作用：在线性时间内维护定长区间的最值。单调队列没学过的话去学一下这题吧

转移的时候dp[i][k]->dp[i+1][j],k与j的差距不超过T，分两种情况转移，k在j的左边和右边，所以维护T长度的最值，双向扫一遍就OK了

（从右边扫过来）

k j j k

<--------T-------> <--------T------->

dp[i+j][j]=max(dp[i][k]+sum[i+1][j]-sum[i][k-1]) sum[i][j]为第i行的前j项和 所以可以维护一个dp[i][k]-sum[i][k-1]的最大值，每到一个位置j，在区间长度合法的情况下用维护的最大值mx+sum[i+1][j]来更新dp[i+1][j]

从右往左再来一遍即可

具体边界必须要想清楚

 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 10010;const int inf = ~0u>>2;struct DQ{    int f,r;    int c[maxn];    int v[maxn];    void init(){f=0;r=-1;}    inline void check(int cc){        while(f<=r && c[f]<cc) f++;    }    inline void push(int cc,int vv)    {        while(f<=r && v[r]<=vv) r--;        c[++r]=cc;        v[r]=vv;    }    void print()    {        printf("f==%d r==%d\n",f,r);        for(int i=f;i<=r;i++)        {            printf("(%d,%d)",c[i],v[i]);        }        puts("");    }}q,ql,qr;int dp[maxn],tmp[maxn];int sum[maxn];int main(){    int n,m,x,t;    //printf("%d\n",inf);    while(scanf("%d%d%d%d",&n,&m,&x,&t)!=EOF)    {        fill(dp,dp+m+1,-inf);        dp[x]=0;        for(int i=1;i<=n;i++)        {            sum[0]=0;            q.init();            memcpy(tmp,dp,sizeof(dp));            fill(dp,dp+m+1,-inf);            for(int j=1;j<=m;j++)            {                scanf("%d",&sum[j]);                q.push(j,tmp[j]-sum[j-1]);                sum[j]+=sum[j-1];                int cc=j-t;                if(cc>=1) q.check(cc);                dp[j]=max(dp[j],q.v[q.f]+sum[j]);            }            q.init();            for(int j=m;j>=1;j--)            {                q.push(m-j+1,tmp[j]+sum[j]);                int cc=m-j+1-t;                if(cc>=1) q.check(cc);                dp[j]=max(dp[j],q.v[q.f]-sum[j-1]);            }        }        int ans=-inf;        for(int i=1;i<=m;i++)        {            if(dp[i]>ans) ans=dp[i];        }        printf("%d\n",ans);    }    return 0;}