Trade-----HSU 3401----単調キュー最適化DP

タイトルアドレス:http://acm.hdu.edu.cn/showproblem.php?pid=3401
タイトル:
T日があって、あなたは毎日APIで买うことができて、BPIは売って、最大ASI个を买って、最大BSI个を売ります
MAXPの商品は最大2つしか持っていません.隣接する2つの取引はW日より大きいです.
T日目の終わりにいくら稼げるか聞いてみましょう
問題解決の考え方:
3つの状態遷移方程式があり、そのうちdp[i][j]はi日目にj個の商品を手に入れたときに稼いだお金を表す.
dp[i][j] = max(dp[i][j],dp[i-1][j])  //前日に向けて何もしない
買うにはプッシュがあります
dp[i][j] = max(dp[i][j],max(dp[i-w-1][k] - (j-k)*buyp[i]  )
さらに分解するとdp[i][j]=max(dp[i][j],max(dp[i-w-1][k]+k*buyp[i])-j*buyp[i]);
買うので0<=(j-k)<=canbuyn[i]
優先キューを使用して、iにとって見られる最大のキューをキューの先頭に置くことができます.
売るには同じ理屈だが、方程式が
dp[i][j] = max(dp[i][j], max(dp[i-w-1][k]+k*sellp[i])-j*sellp[i]
0<=(k-j)<=canselln[i]
次のコードは次のとおりです.
 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;

const int maxn = 3000;

struct node
{
    int val,pos;
}q[maxn];

int sellp[maxn],buyp[maxn];
int canselln[maxn],canbuyn[maxn];
int dp[maxn][maxn];
int T,n,maxp,w;
const int inf = 0x3f3f3f3f;

void dpf()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=maxp;j++)
            dp[i][j] = -inf;
    }

    //  w+1    ，   
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=min(maxp,canbuyn[i]);j++)
        {
            dp[i][j] = -buyp[i]*j;  //      
        }
    }

    for(int i=2;i<=n;i++) //          
    {
        for(int j=0;j<=maxp;j++)
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
    }

    for(int i=w+2;i<=n;i++)   // w+1         ，        w+2  
    {
        int pre = i-w-1;
        //     ，      
        //dp[i][j] = max(dp[i][j],max(dp[i-w-1][k] - (j-k)*buyp[i]  )
        //        dp[i][j] = max(dp[i][j], max(dp[i-w-1][k]+k*buyp[i]) - j*buyp[i] );
        //    ，  0<=(j-k)<=canbuyn[i]
        //             i            
        int head,tail;
        head = 0;
        tail = -1;
        for(int j=0;j<=maxp;j++)
        {
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
            node tmp;
            tmp.val = dp[pre][j]+j*buyp[i];
            tmp.pos = j;
            //          
            while(head<=tail && q[tail].val < tmp.val) tail--;
            q[++tail] = tmp;
            //      0<=(j-k)<=canbuyn[i]
            while(head<=tail && (j-q[head].pos)>canbuyn[i] )head++;

            //   
            if(head<=tail) dp[i][j] = max(dp[i][j],q[head].val-j*buyp[i]);
        }

        //       ，       
        //dp[i][j] = max(dp[i][j], max(dp[i-w-1][k]+k*sellp[i])-j*sellp[i]
        //0<=(k-j)<=canselln[i]
        head=0;
        tail=-1;
        for(int j=maxp;j>=0;j--)
        {
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
            node tmp;
            tmp.val = dp[pre][j]+j*sellp[i];
            tmp.pos = j;

            while(head<=tail && q[tail].val < tmp.val) tail--;
            q[++tail] = tmp;

            while(head<=tail && (q[head].pos-j) > canselln[i]) head++;

            if(head<=tail) dp[i][j] = max(dp[i][j],q[head].val-j*sellp[i]);

        }


    }

}


int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&maxp,&w);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d%d",&buyp[i],&sellp[i],&canbuyn[i],&canselln[i]);
        dpf();
        int ans = 0;
        for(int j=0;j<=maxp;j++)
            ans = max(ans,dp[n][j]);
        printf("%d
",ans);
    }
    return 0;
}