HDU 3401 Trade dp+單調隊列優化

題目連結：

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

Trade

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

#### 問題描述

> Recently, lxhgww is addicted to stock, he finds some regular patterns after a few days' study.

> He forecasts the next T days' stock market. On the i'th day, you can buy one stock with the price APi or sell one stock to get BPi.

> There are some other limits, one can buy at most ASi stocks on the i'th day and at most sell BSi stocks.

> Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i'th day, the next trading day must be on the (i+W+1)th day or later.

> What's more, one can own no more than MaxP stocks at any time.

>

> Before the first day, lxhgww already has infinitely money but no stocks, of course he wants to earn as much money as possible from the stock market. So the question comes, how much at most can he earn?

輸入

The first line is an integer t, the case number.

The first line of each case are three integers T , MaxP , W .

(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .

The next T lines each has four integers APi，BPi，ASi，BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.

輸出

The most money lxhgww can earn.

樣例輸入

1

5 2 0

2 1 1 1

3 2 1 1

4 3 1 1

5 4 1 1

樣例輸出

3

題意

一個人，一開始有無數的錢和0張股票，接下來的t天裡，在第i天，他能夠選擇以api的價格買進一張股票，且最多允許買asi張；或者以bpi的價格賣出股票，且最多賣出bpi張。任何時刻手頭的股票不能超過maxp張，且任意兩次交易需要隔至少w天。問最多能賺多少錢。

題解

dp[i][j]表示第i天持有j張股票。

則易知:

dp[i][j]=max{dp[i-1][j],dp[i-w-1][k]-(j-k)*api(買入),dp[i-w-1][k]+(k-j)*bpi)(賣出)}

因為當j固定時隻需找出max{dp[i-w-1][k]+k*api(或者bpi)}，由于有asi(或者bsi)的限制，是以需要用單調隊列來維護一下(否則隻需要維護一個最大值就ok了)。是以複雜度是O^2。

代碼

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf

typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=2222;

int n,maxp,w;
int ap[maxn],bp[maxn],as[maxn],bs[maxn];
///dp[i][j]表示第i天持j張股票
int dp[maxn][maxn];
///單調隊列
PII que[maxn];

int main() {
    int tc;
    scf("%d",&tc);
    while(tc--){
        scf("%d%d%d",&n,&maxp,&w);
        for(int i=0;i<n;i++){
            scf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
        }

        ///初始化
        for(int i=0;i<n;i++){
            for(int j=0;j<=maxp;j++){
                dp[i][j]=-INF;
            }
        }
        for(int j=0;j<=min(maxp,as[0]);j++){
            dp[0][j]=-ap[0]*j;
        }

        for(int i=1;i<n;i++){
            ///第i天不進行交易
            for(int j=0;j<=maxp;j++){
                dp[i][j]=dp[i-1][j];
            }

            ///第i天進行交易
            if(i-w-1<0){
                for(int j=0;j<=min(maxp,as[i]);j++){
                    dp[i][j]=max(dp[i][j],-ap[i]*j);
                }
                continue;
            }

            ///買入
            int f=1,r=1;
            for(int j=0;j<=maxp;j++){
                int x=dp[i-w-1][j]+ap[i]*j;
                while(f<r&&que[r-1].X<x) r--;
                que[r++]=mkp(x,j);
                while(f<r&&que[f].Y+as[i]<j) f++;
                dp[i][j]=max(dp[i][j],que[f].X-j*ap[i]);
            }

            ///賣出
            f=r=1;
            for(int j=maxp;j>=0;j--){
                int x=dp[i-w-1][j]+bp[i]*j;
                while(f<r&&que[r-1].X<x) r--;
                que[r++]=mkp(x,j);
                while(f<r&&que[f].Y-bs[i]>j) f++;
                dp[i][j]=max(dp[i][j],que[f].X-j*bp[i]);
            }
        }
        int ans=0;
        for(int i=0;i<=maxp;i++){
            ans=max(ans,dp[n-1][i]);
        }
        prf("%d\n",ans);
    }
    return 0;
}

//end-----------------------------------------------------------------------