[Scoi2010]股票交易(dp的不斷優化/單調隊列優化dp)

傳送門

題意：直接看題意即可

題解：首先，第一步可以想到的是dp，用dp[i][j]表示在第i天下有j張票的最大錢數，然後按照時間順序dp下去，複雜度o(t^2mp^2)，隻能得到40分。

附上代碼：

#include<bits/stdc++.h>

using namespace std;

const int MAX=2e3+50;

int t,mp,w;
int dp[MAX][MAX];
int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int main()
{
    scanf("%d%d%d",&t,&mp,&w);
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d",&vb[i],&vs[i],&lb[i],&ls[i]);
    }
    memset(dp,-63,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=max(0,i-w-1);j++){
            for(int k=0;k<=mp;k++){
                for(int l=0;k+l<=mp&&l<=lb[i];l++){
                    dp[i][k+l]=max(dp[i][k+l],dp[j][k]-l*vb[i]);
                }
                for(int l=0;l<=k&&l<=ls[i];l++){
                    dp[i][k-l]=max(dp[i][k-l],dp[j][k]+l*vs[i]);
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=t;i++){
        ans=max(ans,dp[i][0]);
    }
    cout<<ans<<endl;
    return 0;
}
           

其實沒必要枚舉限制天數，這樣想，dp[i][j]是在第i天擁有j個股票的最大獲利，那麼直接可以遞推前一天dp[i][j]=max(dp[i][j],dp[i-1][j])即可，這樣可以拿到50分

附上代碼：

#include<bits/stdc++.h>

using namespace std;

const int MAX=2e3+50;

int t,mp,w;
int dp[MAX][MAX];
int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int main()
{
    scanf("%d%d%d",&t,&mp,&w);
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d",&vb[i],&vs[i],&lb[i],&ls[i]);
    }
    memset(dp,-63,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=t;i++){
        int j=max(0,i-w-1);
        for(int k=0;k<=mp;k++){
            dp[i][k]=max(dp[i][k],dp[i-1][k]);
            for(int l=0;k+l<=mp&&l<=lb[i];l++){
                dp[i][k+l]=max(dp[i][k+l],dp[j][k]-l*vb[i]);
            }
            for(int l=0;l<=k&&l<=ls[i];l++){
                dp[i][k-l]=max(dp[i][k-l],dp[j][k]+l*vs[i]);
            }
        }
    }
    cout<<dp[t][0]<<endl;
    return 0;
}
           

其實還可以發現，在前W天隻能買或者不買，那麼再優化一下，就可以拿到70分了

附上代碼：

#include<bits/stdc++.h>

using namespace std;

const int MAX=2e3+50;

int t,mp,w;
int dp[MAX][MAX];
int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int main()
{
    scanf("%d%d%d",&t,&mp,&w);
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d",&vb[i],&vs[i],&lb[i],&ls[i]);
    }
    memset(dp,-63,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=lb[i];j++){
            dp[i][j]=-j*vb[i];
        }
        for(int j=0;j<=mp;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
        if(i<=w){
            continue;
        }
        int j=max(0,i-w-1);
        for(int k=0;k<=mp;k++){
            dp[i][k]=max(dp[i][k],dp[i-1][k]);
            for(int l=0;k+l<=mp&&l<=lb[i];l++){
                dp[i][k+l]=max(dp[i][k+l],dp[j][k]-l*vb[i]);
            }
            for(int l=0;l<=k&&l<=ls[i];l++){
                dp[i][k-l]=max(dp[i][k-l],dp[j][k]+l*vs[i]);
            }
        }
    }
    cout<<dp[t][0]<<endl;
    return 0;
}
           

最後可以發現，如果買股票的話，對于每個dp[i][j]=max(dp[x][k]-(j-k)*v)，展開為dp[i][j]=max(dp[x][k]+k*v-j*v)，又可以發現j*v始終是j*v，是以可以移動外面，dp[i][j]=max(dp[x][k]+k*v)-j*v，是以此時通過單調隊列進行維護max(dp[x][k]+k*v)，同理，如果賣股票的話，dp[i][j]=max(dp[x][k]+(k-j)*v)，展開dp[i][j]=max(dp[x][k]+k*v-j*v)，發現j*v沒關系，轉到外面，dp[i][j]=max(dp[x][k]+k*v)+j*v，然後，還是通過單調隊列進行維護max(dp[x][k]+k*v)，而此時的方向需要從後往前進行維護。

附上代碼：

#include<bits/stdc++.h>

using namespace std;

const int MAX=2e3+50;

int t,mp,w;
int dp[MAX][MAX];
int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int deq[MAX];

int main()
{
    scanf("%d%d%d",&t,&mp,&w);
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d",&vb[i],&vs[i],&lb[i],&ls[i]);
    }
    memset(dp,-63,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=lb[i];j++){
            dp[i][j]=-j*vb[i];
        }
        for(int j=0;j<=mp;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
        if(i<=w){
            continue;
        }
        int x=i-w-1,head=0,tail=0;
        for(int j=0;j<=mp;j++){
            while(head<tail&&deq[head]<j-lb[i]){
                head++;
            }
            while(head<tail&&dp[x][deq[tail-1]]+deq[tail-1]*vb[i]<=dp[x][j]+j*vb[i]){
                tail--;
            }
            deq[tail++]=j;
            if(head<tail){
                dp[i][j]=max(dp[i][j],dp[x][deq[head]]+deq[head]*vb[i]-j*vb[i]);
            }
        }
        head=tail=0;
        for(int j=mp;j>=0;j--){
            while(head<tail&&deq[head]>j+ls[i]){
                head++;
            }
            while(head<tail&&dp[x][deq[tail-1]]+deq[tail-1]*vs[i]<=dp[x][j]+j*vs[i]){
                tail--;
            }
            deq[tail++]=j;
            if(head<tail){
                dp[i][j]=max(dp[i][j],dp[x][deq[head]]+deq[head]*vs[i]-j*vs[i]);
            }
        }
    }
    cout<<dp[t][0]<<endl;
    return 0;
}