hdu-3401-Trade-單調隊列優化的DP

單調隊列入門題。。。

dp[i][j]:第i天，手中擁有j個股票時，獲得的最大利潤。

若第i天不買不賣：dp[i][j]=max(dp[i][j],dp[i-1][j]);

若第i天買 ：dp[i][j]=max(dp[i][j],dp[i-w-1][k]-(j-k)*ap[i]);

若第i天賣 ：dp[i][j]=max(dp[i][j],dp[i-w-1][k]+(k-j)*bp[i]);

若只考慮買的情況：
dp[i][j]=dp[i-w-1][k]+ap[i]*k-j*ap[i];

很明顯，可以用單調隊列優化dp[i-w-1][k]+ap[i]*k。

#include
#include
#include
#include
#include
using namespace std;
//#define INF ((1<<30)-1)
#define INF 0xfffff
#define maxn 2200
#define LL long long
#define MOD 1000000009
int dp[2200][2200];
struct list
{
    int val;
    int x;
} p[5001],q;
int ap[maxn],bp[maxn],as[maxn],bs[maxn];
int main()
{
    int Ts;
    int n,m,w,i,j;
    scanf("%d",&Ts);
    while(Ts--)
    {
        scanf("%d%d%d",&n,&m,&w);
        for(i=0; i<=n; i++)
            for(j=0; j<=m; j++)dp[i][j]=-INF;
        int head,tail;
        for(i=1;i<=n;i++)scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
        for(j=1;j<=w+1;j++)
            for(i=0;i<=min(as[j],m);i++)
                dp[j][i]=-1*ap[j]*i;
        for(i=2; i<=n; i++)
        {
            for(j=0;j<=m;j++)dp[i][j]=max(dp[i-1][j],dp[i][j]);
            if(i<=w+1)continue;
            head=1;
            tail=0;
            for(j=0; j<=m; j++)
            {
                q.x=j;
                q.val=dp[i-w-1][j]+ap[i]*j;
                while(tail>=head&&q.val>p[tail].val)tail--;
                p[++tail]=q;
                while(tail>=head&&p[head].x=0;j--)
            {
                q.x=j;
                q.val=dp[i-w-1][j]+bp[i]*j;
                while(tail>=head&&q.val>p[tail].val)tail--;
                p[++tail]=q;
                while(tail>=head&&p[head].x>j+bs[i])head++;
                if(head<=tail)dp[i][j]=max(dp[i][j],p[head].val-bp[i]*j);
            }
        }
        int maxx=0;
        for(i=0;i<=m;i++)maxx=max(maxx,dp[n][i]);
        printf("%d\n",maxx);
    }
    return 0;

}