P2569 [SCOI2010]股票交易

通过一段时间的观察，预测到了未来 n天内某只股票的走势，第 i 天的股票买入价为每股 a[i]​，第 ii 天的股票卖出价为每股 b[i]

（a[i]>=b[i]），

规定第 ii 天的一次买入至多只能购买 as[i]​ 股，一次卖出至多只能卖出 bs[i] 股。

规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 W天，且一个人的手里的股票数不能超过 M。

假设有钱的数量充足（数目无限），但是没有任何股票，求n天后能赚到最多的钱

 f[i][j] =max{ f[x][k] + (k-j) *a[i] }

f[i][j]= ....

 f[i][j] = max{ f[i-W-1][k] + k* a[i] -j *a[i] }  j-as[i] <k<j

 f[i][j] =max( f[i-W-1][k] +k*b[i] -j*b[i] }  j<k<j+bs[i] 

 提出 func(k) = f[i-W-1][k]+ k*array[i] ，滑窗模型

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std; 
 const int N=2004;
 int n,m,W,f[N][N];
 int a[N],b[N],as[N],bs[N];
 
 int func(int i,int k,int *arr){
     int t=i-W-1;
     return f[t][k]+k*arr[i];
 }
 int q[N],hh,tt;
 
 void solve(){
     int i,j,k;
     cin>>n>>m>>W;
     memset(f,128,sizeof f); 
     
     for(i=1;i<=n;i++) 
     cin>>a[i]>>b[i]>>as[i]>>bs[i];
     
     for(i=1;i<=n;i++){
         
         for(j=0;j<=as[i];j++) f[i][j]= -j*a[i];
         for(j=0;j<=m;j++) f[i][j]=max(f[i][j],f[i-1][j]);
         if(i<=W) continue;
         
         hh=1,tt=0;
         for(j=0;j<=m;j++){
              while(hh<=tt&&q[hh]<j-as[i]) hh++;
              while(hh<=tt&&func(i,q[tt],a)<=func(i,j,a)) 
               tt--;
              q[++tt]=j;
              
              if(hh<=tt)
              f[i][j]=max(f[i][j],f[i-W-1][q[hh]]+q[hh]*a[i]-j*a[i]);
        }
        hh=1,tt=0;
        for(j=m;j>=0;j--){
            while(hh<=tt&&q[hh]>j+bs[i]) hh++;
              while(hh<=tt&&func(i,q[tt],b)<=func(i,j,b)) 
               tt--;
              q[++tt]=j;
              
              if(hh<=tt)
              f[i][j]=max(f[i][j],f[i-W-1][q[hh]]+q[hh]*b[i]-j*b[i]);
        }
    }
    int ans=-1e9;
    for(i=0;i<=m;i++) ans=max(ans,f[n][i]);
    cout<<ans<<endl;
 }
 signed main(){
     solve();
 }