HDU 3401 Trade （单调队列优化DP）-程序员宅基地

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3401

题意：炒股。第i天买入一股的价钱api，卖出一股的价钱bpi，最多买入asi股，最多卖出bsi股。两次操作（买入或卖出）中间必须相差W天。炒股时间为n。任意时间手中的股票不大于MaxP。求最大收益。

思路：设dp[i][j]表示到第i天手中持有j股的最大收益，那么有dp[i][j]=max(dp[i-1][j],dp[r][k]+(j-k)*ap[i],dp[r][k]+(k-j)*bp[i])。其中r<=i-W,j-k<=asi,k-j<=bsi。由于dp[i][j]至少为dp[i-1][j],因此上式可简化为dp[i][j]=max(dp[i-1][j],dp[i-W][k]+(j-k)*ap[i],dp[i-W][k]+(k-j)*bp[i])。而dp[i-W][k]+(j-k)*ap[i]=dp[i-W][k]+k*ap[i]-j*ap[i],dp[i-W][k]+(k-j)*bp[i]=dp[i-W][k]+k*bp[i]-j*bp[i]。可用单调队列优化。

int n,MaxP,W;
int ap[N],bp[N],as[N],bs[N];
int dp[N][N];
pair<int,int> a[N];

int cal()
{
    int i,j;
    for(i=1;i<=n;i++) for(j=0;j<=MaxP;j++) dp[i][j]=-INF;
    for(i=1;i<=W;i++) for(j=0;j<=as[i];j++) dp[i][j]=-j*ap[i];
    for(i=2;i<=n;i++)
    {
        if(i<=W)
        {
            for(j=0;j<=MaxP;j++) upMax(dp[i][j],dp[i-1][j]);
            continue;
        }
        int head=0,tail=0;
        for(j=0;j<=MaxP;j++)
        {
            upMax(dp[i][j],dp[i-1][j]);
            pair<int,int> p=MP(j,dp[i-W][j]+j*ap[i]);
            while(head<tail && a[tail-1].second<=p.second) tail--;
            a[tail++]=p;
            while(head<tail && j-a[head].first>as[i]) head++;
            upMax(dp[i][j],a[head].second-j*ap[i]);
        }
        head=0,tail=0;
        for(j=MaxP;j>=0;j--)
        {
            pair<int,int> p=MP(j,dp[i-W][j]+j*bp[i]);
            while(head<tail && a[tail-1].second<=p.second) tail--;
            a[tail++]=p;
            while(head<tail && a[head].first-j>bs[i]) head++;
            upMax(dp[i][j],a[head].second-j*bp[i]);
        }
    }
    int ans=0;
    for(i=0;i<=MaxP;i++) upMax(ans,dp[n][i]);
    return ans;
}

int main()
{
    rush()
    {
        RD(n,MaxP,W); W++;
        int i;
        FOR1(i,n) RD(ap[i],bp[i]),RD(as[i],bs[i]);
        PR(cal());
    }
}