【无标题】2024.6.6

2024.6.6 【一天高考！！！ “夏天周而复始、该相逢的人会再相逢”】

Thursday 五月初一

<theme = oi-“DP”>

来学习一下DP的优化

其实考试时我应该很难用到优化的

P2569 [SCOI2010] 股票交易

DP柿子比较好推，

T，Maxp都比较小，

作为f数组的两维还是挺合理的。

那么设f[i][j]为第i天，有j张票的最大价值

$$\begin{gathered} 没票时买 \\ f[i][j]=-ap[i]\ast j \\ (0\le j\le as[i]) \\ 不参与买卖 \\ f[i][j]=max(f[i][j],f[i-1][j]) \\ (0\le j\le Maxp) \\ 买 \\ f[i][j]=max(f[i][j],f[i-w-1][k]-(j-k)\ast ap[i]) \\ (j-as[i]\le k<j) \\ 卖 \\ f[i][j]=max(f[i][j],f[i-w-1][k]+(k-j)\ast bp[i]) \\ (j<k\le j+bs[i]) \end{gathered}$$

然后就可以利用单调队列优化了

单调队列

//2024.6.6
//by white_ice
//[SCOI2010] 股票交易 | P2569
#include<bits/stdc++.h>
//#include"fopen.cpp"
using namespace std;
#define itn int
constexpr int oo = 2003;

int jntm(itn a,int b){return a>b?a:b;}
int ngm (itn a,int b){return a<b?a:b;}

int t,p,w;
int ap[oo],bp[oo],as[oo],bs[oo];
int f[oo][oo];

itn stk[oo];

int main(){
    //fre();

    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> t >> p >> w;

    memset(f,128,sizeof(f));

    for (itn i=1;i<=t;i++)
        cin >> ap[i] >> bp[i] >> as[i] >>bs[i];
    
    // for (int i=1;i<=t;i++){
    //     for (itn j=0;j<=as[i];j++)
    //         f[i][j] = -1*j*ap[i];
    
    //     for (itn j=0;j<=p;j++)
    //         f[i][j] = jntm(f[i][j],f[i-1][j]);
    //     if (i<=w)
    //         continue;
    //     int l,r;
    //     l = 1;r = 0;
    //     for (itn j=0;j<=p;j++){
    //         while (l<=r&&stk[l]<j-as[i])
    //             l++;
    //         while (l<=r&&f[i-w-1][stk[r]]+stk[r]*ap[i]<=f[i-w-1][j]+j*ap[i]);
    //                   //f[i-w-1][stk[r]]+stk[r]*ap[i]<=f[i-w-1][j]+j*ap[i]
    //             r--;
    //         stk[++r] = j;
    //         if (l<=r)
    //             f[i][j] = jntm(f[i][j],f[i-w-1][stk[l]]+stk[l]*ap[i]-j*ap[i]);
    //     }                            //f[i-w-1][stk[l]]+stk[l]*ap[i]-j*ap[i]

    //     l = 1,r = 0;
    //     for (itn j=p;j>=0;j--){
    //         while (l<=r&&stk[l]>j+bs[i])
    //             l++;
    //         while (l<=r&&f[i-w-1][stk[r]]+stk[r]*bp[i]<=f[i-w-1][j]+j*bp[i])
    //                    //f[i-w-1][stk[r]]+stk[r]*bp[i]<=f[i-w-1][j]+j*bp[i]
    //             r--;
    //         stk[++r] = j;
    //         if (l<=r)
    //             f[i][j] = jntm(f[i][j],f[i-w-1][stk[l]]+stk[l]*bp[i]-j*bp[i]);
    //                                  //f[i-w-1][stk[l]]+stk[l]*bp[i]-j*bp[i]
    //     }
    // }

    for(int i=1;i<=t;i++){
        cin >> ap[i] >> bp[i] >> as[i] >> bs[i];
        for(int j=0;j<=as[i];j++)
            f[i][j] = -1*j*ap[i]; 
        for(int j=0;j<=p;j++)
            f[i][j] = jntm(f[i][j],f[i-1][j]); 
        if(i<=w)
            continue;    
        int l,r;
        
        l = 1 , r = 0;
        for(int j=0;j<=p;j++){
            while(l<=r&&stk[l]<j-as[i])
                l++; 
            while(l<=r&&f[i-w-1][stk[r]]+stk[r]*ap[i]<=f[i-w-1][j]+j*ap[i])
                r--; 
            stk[++r] = j; 
            if (l<=r)
                f[i][j] = jntm(f[i][j],f[i-w-1][stk[l]]+stk[l]*ap[i]-j*ap[i]); 
        }

        l = 1 , r = 0;
        for(int j=p;j>=0;j--){
            while(l<=r&&stk[l]>j+bs[i])
                l++;
            while(l<=r&&f[i-w-1][stk[r]]+stk[r]*bp[i]<=f[i-w-1][j]+j*bp[i])
                r--;
            stk[++r] = j;
            if(l <= r)
                f[i][j] = jntm(f[i][j],f[i-w-1][stk[l]]+stk[l]*bp[i]-j*bp[i]); 
        }
    }

    int out =  -0x3f3f3f3f;

    for (itn i=0;i<=p;i++)
        out = jntm (out,f[t][i]);
    cout << out;
    return 0;
}

对于一个dp方程

如果，dp[i] = i相关项+j相关项(0<=j<=i)

就可以使用单调队列了

单调队列优化