AcWing - 332 - 股票交易 = 单调队列优化dp

标签：更新   end   const   www   empty   复杂度   print   clu   ble   

https://www.acwing.com/problem/content/334/

第一次写单调队列优化的dp，首先朴素的做法不难想到，就是复杂度 \(O(n^3)\) ，然后考虑优化。

每天都从 \(pre=max(0,i-w-1)\) 天转移过来就刚刚好了。

考虑每个k是怎么更新j的。

买入股票：

\(dp[i][j]=max\{dp[pre][k]-(j-k)*AP_i\;|\;k \leq j\;and\;(j-k) \leq AS_i\}\)

\(dp[i][j]=max\{dp[pre][k]+k*AP_i\;|\;k \leq j\;and\;(j-k) \leq AS_i\}-j*AP_i\)

里面的这个k的取值范围随j的增长会滑动，所以用单调队列维护。

#include 
using namespace std;
typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dp[2005][2005];

deque AQ, BQ;

int AP, BP;

ll Calc_A(int id1, int id2) {
    return dp[id1][id2] + 1ll * id2 * AP;
}
ll Calc_B(int id1, int id2) {
    return dp[id1][id2] + 1ll * id2 * BP;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int T, maxP, W;
    scanf("%d%d%d", &T, &maxP, &W);
    memset(dp, -INF, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i = 0; --j) {
            while(Bk >= j) {
                ll tmp = Calc_B(pre, Bk);
                while(!BQ.empty() && Calc_B(pre, BQ.back())  BS + j))
                BQ.pop_front();
            if(!BQ.empty())
                dp[i][j] = max(dp[i][j], Calc_B(pre, BQ.front()) - 1ll * j * BP);
            //cout

AcWing - 332 - 股票交易 = 单调队列优化dp

标签：更新   end   const   www   empty   复杂度   print   clu   ble   

原文地址：https://www.cnblogs.com/Inko/p/11514276.html