P2569 [SCOI2010] 股票交易（ST表+dp）

Makerlike · 2024-08-26 20:25:34 · 题解

前言

奔着单调队列优化dp来的，看完讨论版发现线段树优化也可以，但是线段树常数大，我们不妨用ST表：

思路

一眼dp题，直接考虑状态转移方程， F(i,j)表示第 i天踹了j个股票，一共有以下四种状态，别的题解讲过了，所以这里不细讲，简单罗列一下：

1.不买也不卖：

直接继承上一天的状态

2.凭空买

负的每股的价格*当天买来的股票数，就是

3.在之前基础上买股票

设买了 k股股票，范围 (j-ASi<=k<j) ，得出 F(i,j)=max{F(i-W-1,k)-(j-k)*APi}

4.在之前基础上卖股票

设卖了 k股股票，范围 (j<k<=j+BSi) 得出 F(i,j)=max{F(i-W-1,k)+(k-j)*BPi}

拆项

维护 F(i-W-1,k)+k*APi 与F(i-W-1,k)+k*BPi 的最小值便行了

打进ST表

不会的小朋友戳 这里 注意一个点，本题是能取0的，所以ST表要从0开始存，以下是ST表部分代码：

struct ST{
    int f1[N][20],f2[N][20];
    void build(int x){
        for(int i=0;i<=mxp;i++){
            f1[i+1][0]=dp[x][i]+i*ap;
            f2[i+1][0]=dp[x][i]+i*bp;
        }
        for(int j=1;(1<<j)<=mxp+1;j++){
            for(int i=1;i+(1<<j)-1<=mxp+1;i++){
                f1[i][j]=max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
                f2[i][j]=max(f2[i][j-1],f2[i+(1<<j-1)][j-1]);
            }
        }
    }
    int query_1(int l,int r){
        l++,r++;
        int k=log2(r-l+1);
        return max(f1[l][k],f1[r-(1<<k)+1][k]);
    }
    int query_2(int l,int r){
        l++,r++;
        int k=log2(r-l+1);
        return max(f2[l][k],f2[r-(1<<k)+1][k]);
    }
}s;

完整代码

希望能给大家带来帮助！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e3+10;
const int INF=0x3f3f3f3f;
int n,mxp,w,ap,bp,as,bs,dp[N][N];
struct ST{
    int f1[N][20],f2[N][20];
    void build(int x){
        for(int i=0;i<=mxp;i++){
            f1[i+1][0]=dp[x][i]+i*ap;
            f2[i+1][0]=dp[x][i]+i*bp;
        }
        for(int j=1;(1<<j)<=mxp+1;j++){
            for(int i=1;i+(1<<j)-1<=mxp+1;i++){
                f1[i][j]=max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
                f2[i][j]=max(f2[i][j-1],f2[i+(1<<j-1)][j-1]);
            }
        }
    }
    int query_1(int l,int r){
        l++,r++;
        int k=log2(r-l+1);
        return max(f1[l][k],f1[r-(1<<k)+1][k]);
    }
    int query_2(int l,int r){
        l++,r++;
        int k=log2(r-l+1);
        return max(f2[l][k],f2[r-(1<<k)+1][k]);
    }
}s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(dp,-0x3f,sizeof(dp));
    cin>>n>>mxp>>w;
    for(int i=1;i<=n;i++){
        cin>>ap>>bp>>as>>bs;
        for(int j=0;j<=as;j++)
            dp[i][j]=-1*ap*j;
        for(int j=0;j<=mxp;j++)
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        if(i<=w) continue;
        s.build(i-w-1);
        for(int j=0;j<=mxp;j++)
            dp[i][j]=max(dp[i][j],s.query_1(max(j-as,0),j)-j*ap);
        for(int j=0;j<=mxp;j++)
            dp[i][j]=max(dp[i][j],s.query_2(j,min(j+bs,mxp))-j*bp);
    }
    int ans=-INF;
    for(int i=0;i<=mxp;i++)
        ans=max(ans,dp[n][i]);
    cout<<ans<<'\n';
    return 0;
}

后记

发现我的思路一直很奇怪，别人用tarjan，我用我的玄学线段树；别人用单调队列，而我用st表…… 学习多种方法总是有益的！！！