P2569 [SCOI2010]股票交易

Problem

初始有(infty)元钱，有(T)天，每天可以买卖股票，告诉你第(i)天股票买入价(AP_i)，股票卖出价(BP_i)（保证(AP_i ge BP_i)），至多买(AS_i)股，至多卖出(BS_i)股。股票交易至少要间隔(W)天，每天一个人手里的股票数不得超过(MaxP)。求(T)天后最大赚钱数。
(1 le BP_i le AP_i le 1000,1 le AS_i,BS_i le MaxP,0 le W < T le 50,1 le MaxP le 50)。

Solution

不难想到设(dp[i][j])为到第(i)天手上有(j)股股票时的最大赚钱数。接下来分类讨论：

前面啥也不干，第(i)天突然买入(j)股股票:(dp[i][j] = -AP[i] cdot j)。
第(i)天啥也不干：(dp[i][j] = dp[i - 1][j])
第(i)天买入：

[dp[i][j] = max_{j - AS_i le k le j - 1} {dp[i - W - 1][k] - AP_i cdot (j - k) } = max_{j - AS_i le k le j - 1} {dp[i - W - 1][k] + AP_i cdot k} - AP_i cdot j ]

第(i)天卖出：

[dp[i][j] = max_{j + 1 le k le BS_i + j} {dp[i - W - 1][k] + BP_i cdot (k - j)} = max_{j + 1 le k le BS_i + j} {dp[i - W - 1][k] + BP_i cdot k} - BP_i cdot j ]

两个东西分别维护单调队列跑一遍，注意卖出的情况得从后往前扫。

# include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int T,MaxP,W,AP[N],BP[N],AS[N],BS[N];
int dp[N][N];
int q[N << 2],head = 1,tail = 0;

int main(void)
{
    scanf("%d%d%d",&T,&MaxP,&W);
    for(int i = 1; i <= T; i++)
    {
        scanf("%d%d%d%d",&AP[i],&BP[i],&AS[i],&BS[i]);
    }
    memset(dp,0xcf,sizeof(dp)); 
    // for(int i = 1; i <= T; i++) dp[i][0] = 0;
    for(int i = 1; i <= T; i++) 
    {
        for(int j = 0; j <= AS[i]; j++) dp[i][j] = -AP[i] * j;
        for(int j = 0; j <= MaxP; j++) dp[i][j] = max(dp[i][j],dp[i - 1][j]);
        if(i - W - 1 >= 0)
        {
            head = 1,tail = 0;
            for(int j = 0; j <= MaxP; j++) 
            {
                while(head <= tail && q[head] < j - AS[i]) ++head;
                while(head <= tail && dp[i - W - 1][j] + AP[i] * j >= dp[i - W - 1][q[tail]] + AP[i] * q[tail]) -- tail;
                q[++tail] = j;
                if(head <= tail) dp[i][j] = max(dp[i][j],dp[i - W - 1][q[head]] + AP[i] * q[head] - AP[i] * j);
            }
            head = 1,tail = 0;
            for(int j = MaxP; j >= 0; j--)
            {
                while(head <= tail && q[head] > BS[i] + j) ++head;
                while(head <= tail && dp[i - W - 1][j] + BP[i] * j >= dp[i - W - 1][q[tail]] + BP[i] * q[tail]) --tail;
                q[++tail] = j;
                if(head <= tail) dp[i][j] = max(dp[i][j],dp[i - W - 1][q[head]] + BP[i] * q[head] - BP[i] * j);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= MaxP; i++) ans = max(ans,dp[T][i]);
    printf("%d
",ans);
    return 0;
}

[]