原题来自：SCOI 2010
最近 lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww 预测到了未来 T 天内某只股票的走势，第 ii 天的股票买入价为每股 APi ，第 i 天的股票卖出价为每股 BPi （数据保证对于每个 i，都有 APi≥BPi ），但是每天不能无限制地交易，于是股票交易所规定第 i 天的一次买入至多只能购买 ASi 股，一次卖出至多只能卖出 BSi 股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 W 天，也就是说如果在第 i 天发生了交易，那么从第 i+1 天到第 i+W 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 MaxP。
在第一天之前，lxhgww 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T 天以后，lxhgww 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？
输入数据第一行包括三个整数，分别是 T,MaxP,W。
接下来 T 行，第 i 行代表第 i?1 天的股票走势，每行四个整数，分别表示 APi,BPi,ASi,BSi 。
输出数据为一行，包括一个数字，表示 lxhgww 能赚到的最多的钱数。
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
3
数据范围与提示：
对于 30% 的数据，0≤W<T≤50,1≤MaxP≤50；
对于 50% 的数据，0≤W<T≤2000,1≤MaxP≤50；
对于 100% 的数据，0≤W<T≤2000,1≤MaxP≤2000,1≤BPi?≤APi?≤1000,1≤ASi?,BSi?≤MaxP。
sol：一本通居然没有数据范围太优秀了
很容易发现可以dp，dp[i][j]表示到第i个位置，有j张股票最多赚多少钱
先考虑暴力dp
1）：dp[i][j]由dp[i-1][j]直接转移过来，dp[i][j]=max（dp[i][j],dp[i-1][j]）
2）：直接从0开始买股票 dp[i][j]=max（dp[i][j],j*AP） （0<j≤MaxP）
3）：买股票，股票从 k 张变为 j 张，dp[i][j]=max（dp[i][j],dp[i-W-1][k]-(j-k)*AP）
4）：卖股票，股票从 k 张变成 j 张，dp[i][j]=max（dp[i][j],dp[i-W-1][k]+(k-j)*BP）
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } inline void writeln(ll x) { write(x); putchar(‘\n‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) writeln(x) const int N=2005; int T,MaxP,W; int dp[N][N]; int main() { // freopen("trade1.in","r",stdin); int i,j,k; R(T); R(MaxP); R(W); memset(dp,-63,sizeof dp); for(i=1;i<=T;i++) { int AP=read(),BP=read(),AS=read(),BS=read(); for(j=1;j<=min(AS,MaxP);j++) dp[i][j]=-1*AP*j; for(j=0;j<=MaxP;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]); if(i<=W+1) continue; for(j=1;j<=MaxP;j++) { for(k=max(j-AS,0);k<j;k++) { dp[i][j]=max(dp[i][j],dp[i-W-1][k]-AP*(j-k)); /* dp[i][j]=max(dp[i][j],dp[i-W-1][k]-AP*j+AP*k); dp[i][j]=max(dp[i][j],(dp[i-W-1][k]+AP*k)-AP*j) (dp[i-W-1][k]+AP*k)最大的单调队列队首 */ } } for(j=0;j<MaxP;j++) { for(k=j+1;k<=min(MaxP,j+BS);k++) { dp[i][j]=max(dp[i][j],dp[i-W-1][k]+(BP*(k-j))); /* dp[i][j]=max(dp[i][j],dp[i-W-1][k]+BP*k-BP*j); dp[i][j]=max(dp[i][j],(dp[i-W-1][k]+BP*k)-BP*j); (dp[i-W-1][k]+BP*k)最大的单调队列队首 */ } } } Wl(max(dp[T][0],0)); return 0; } /* input 5 2 0 2 1 1 1 2 1 1 1 3 2 1 1 4 3 1 1 5 4 1 1 output 3 */
然后因为这是暴力dp转移，复杂度是T*MaxP*MaxP，可以得到70pts的好成绩
单调队列优化
把式子拆开可得如下（暴力代码注释）
dp[i][j]=max(dp[i][j],dp[i-W-1][k]-AP*j+AP*k);
dp[i][j]=max(dp[i][j],(dp[i-W-1][k]+AP*k)-AP*j)
所以可以维护一个单调队列，(dp[i-W-1][k]+AP*k)最大的单调队列队首
另一个同理
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } inline void writeln(ll x) { write(x); putchar(‘\n‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) writeln(x) const int N=2005,inf=0x3f3f3f3f; int T,MaxP,W; int dp[N][N]; struct Record { int Shuz,Weiz; }Ddq[N]; int main() { // freopen("trade1.in","r",stdin); int i,j,Head,Tail; R(T); R(MaxP); R(W); memset(dp,-63,sizeof dp); for(i=1;i<=T;i++) { int AP=read(),BP=read(),AS=read(),BS=read(); for(j=1;j<=min(AS,MaxP);j++) dp[i][j]=-1*AP*j; for(j=0;j<=MaxP;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]); if(i<=W+1) continue; Head=1; Tail=0; for(j=0;j<=MaxP;j++) { while(Head<Tail&&Ddq[Head].Weiz<j-AS) Head++; while(Head<=Tail&&dp[i-W-1][j]+AP*j>Ddq[Tail].Shuz) Tail--; Ddq[++Tail]=(Record){dp[i-W-1][j]+AP*j,j}; dp[i][j]=max(dp[i][j],Ddq[Head].Shuz-j*AP); } Head=1; Tail=0; for(j=MaxP;j>=0;j--) { while(Head<Tail&&Ddq[Head].Weiz>j+BS) Head++; while(Head<=Tail&&dp[i-W-1][j]+BP*j>Ddq[Tail].Shuz) Tail--; Ddq[++Tail]=(Record){dp[i-W-1][j]+BP*j,j}; dp[i][j]=max(dp[i][j],Ddq[Head].Shuz-j*BP); } } int ans=0; for(i=0;i<=MaxP;i++) ans=max(ans,dp[T][i]); Wl(ans); return 0; } /* input 5 2 0 2 1 1 1 2 1 1 1 3 2 1 1 4 3 1 1 5 4 1 1 output 3 */
原文：https://www.cnblogs.com/gaojunonly1/p/10381300.html
