股票交易题解

littleqwq · 2024-03-31 11:59:41 · 算法·理论

股票交易题解

大致思路：

这道题一眼动态规划，我们来设一个状态，设 dp_{i,j} 为前 i 天拥有股票数量 j 的最大收益，而状态转移方程需要分类讨论。

• 一直单纯买，那么转移方程很明显，一开始我们会将所有数据初始为极小的数，为 dp_{i,j} = j × ap_i。

• 不买也不卖，那么状态转移方程由上面方法转移而来，非常明显，与前一天中找收益大的，转移方程为 dp_{i,j} = \max(dp_{i,j},dp_{i - 1,j})。

• 在上面两种方法的情况下买股票，这个转移方程稍微复杂一些，由于每次买卖之间需要相隔 w 天，也就是上一次进行是在第 i - w - 1 天，我们假设第 i - w - 1 天拥有 k 张股票，而 k 一定比 j 小，因为股票买的要尽可能多，所以，但又不能太多，限制最多 as 张，所以底线是 j - as，而本次共买了 j - k 张股票，要用去 (j - k) × ap_i 元，那么转移方程就是 dp_{i,j} = \max(dp_{i - w - 1,k} - (j - k) × ap_i,dp_{i,j})。

• 在最上面两种情况下卖股票，道理与上一样，就不细讲了，得出转移方程 dp_{i,j} = \max(dp_{i - w - 1,k} + (j - k) × bp_i,dp_{i,j})。

而以上转移方程，需要在 O(n ^ 3) 的时间复杂度下完成，一看数据 2000 ^ 3 肯定过不了。

那么我们需要优化，在下面两种情况中优化，因为那些方程符合单调性优化，以第三种情况为准，用分配律 dp_{i,j} = \max(dp_{i - w - 1,k} + k × ap_i,dp_{i,j}) - j × ap_i。第四种情况也是如此，再用单调队列优化，现在时间复杂度降为了 O(n)，可以通过。

代码实现：

n = read();
    maxp = read();
    w = read();
    memset(dp, -0x3f, sizeof dp);
    q.clear();
    for(int i = 1;i <= n;i ++)
    {
        int l = 1, r = 0; 
        ap = read();
        bp = read();
        as = read();
        bs = read();
        for(int j = 0;j <= as; j ++)//方案1 
        {
            dp[i][j] = (-ap) * j;
        }
        for(int j = 0;j <= maxp;j ++)//方案2 
        {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        }
        if(i <= w) continue;//防越界

        for(int j = 0;j <= maxp;j ++) //方案3 
        {
            while(q.size() && q.front() < j - as)   q.pop_front();
            while(q.size() && dp[i - w - 1][q.back()] + q.back() * ap <= dp[i - w - 1][j] + j * ap) q.pop_back();
            q.push_back(j);
            if(q.size()) dp[i][j] = max(dp[i][j], dp[i - w - 1][q.front()] + ap * q.front() - j * ap);
        }
        q.clear();
        l = 1, r = 0;
        for(int j = maxp;j >= 0;j --)//方案4 
        {
            while(q.size() && q.front() > j + bs)   q.pop_front();
            while(q.size() && dp[i - w - 1][q.back()] + q.back() * bp <= dp[i - w - 1][j] + j * bp) q.pop_back();
            q.push_back(j);
            if(q.size()) dp[i][j] = max(dp[i][j], dp[i - w - 1][q.front()] + bp * q.front() - j * bp);
        }
        q.clear();
    }
    for(int i = 0;i <= maxp;i ++)
    {
        res = max(res, dp[n][i]);
        //cout << dp[n][i] << "\n";
    }
    write(res);