20230705
单调队列优化DP
HDU 3401 Trade
题目大意
传送门
有T天，第i天买股票花Api元，卖股票花Bpi元，最多能买Asi股，
能卖Bsi股。任何时候股票持有量不得超过MaxP，且两个交易日至
少要间隔W天。
若开始时有无限块钱，最后最多能赚多少钱？
（你都有无限块钱了怎么赚都不会增加啊）
0 <= W < T <= 2000, 1 <= MaxP <= 2000
1<=BPi<=APi<=1000, 1<=ASi,BSi<=MaxP
Solution
差一点点就自己写出来啦
很明显，我们考虑写DP
先令\(dp[i][j]\)表示现在是第\(i\)天，手上有\(j\)张股票时最大赚的钱数
那么
\(dp[i][j]=max\left\{\begin{matrix}
dp[i-1][j] \\
dp[i-W-1][k]-(j-k)* Ap[i] \\
dp[i-W-1][k]+(k-j)* Bp[i]
\end{matrix}\right.\)
三种情况分别对应什么都不做、买股票和卖股票
而由于\(dp[i-W-1][k]\)记录的是\(i-W-1\)之前的最优解
所以我们不用再枚举\(i-W-1\)之前的解了
现在考虑优化掉\(k\)这一维
由于\(k\)表示的是手上有多少张股票
所以\(dp[i-W-1][k]\)是单调不下降的
这样就可以考虑用单调队列来维护
先来考虑买股票的情况
在枚举每一个\(i\)的过程中
对于当前枚举到的\(j\)
我们想要\(O(1)\)求得在\(dp[i-W-1][0 \sim j]\)中
使得\(dp[i-W-1][k]+k* Ap[i]\)最大的这个数\(k\)
最后更新dp时减去\(j* Ap[i]\)即可
考虑用单调队列来维护
由于\(dp[i-W-1][j]\)是可以直接转移到\(dp[i][j]\)的
而\(j\)又是不断增大的
在每一次入队时
我们考虑在这个状态下\(dp[i-W-1][j]\)与队尾的所计算的答案比较是否更优
如果更优我们就弹出队尾
这样就可以保证单调队列的正确性
而队首出队就只用判断是否可以转移到\(j\)即可
再来考虑卖股票的情况
由于我们需要的是\(k-j\)
所以需要倒序枚举
其他的操作和买股票基本一致
注意：
队列初始化时不能出错\(head=1,tail=0\)！！！
H_W_Y-Coding
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005,inf=0x3f3f3f3f;
int t,T,W,mxp,Ap[maxn],Bp[maxn],As[maxn],Bs[maxn];
int dp[maxn][maxn],ans=0,q[maxn*2],head,tail;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int main(){
/*2023.7.5 H_W_Y HDU3401 Trade 单调队列优化DP*/
t=read();
while(t--){
T=read();mxp=read();W=read();
for(int i=1;i<=T;i++) {
Ap[i]=read();Bp[i]=read();As[i]=read();Bs[i]=read();
for(int j=0;j<=mxp;j++) dp[i][j]=dp[0][j]=-inf;
}
for(int i=1;i<=W+1;i++)
for(int j=0;j<=min(As[i],mxp);j++)
dp[i][j]=-j*Ap[i];
dp[0][0]=0;
for(int i=1;i<=T;i++){
for(int j=0;j<=mxp;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
if(i<=W+1) continue;
head=1;tail=0;
for(int j=0;j<=mxp;j++){
while(head<=tail&&q[head]+As[i]<j) head++;
if(q[head]<=j) dp[i][j]=max(dp[i][j],dp[i-W-1][q[head]]-(j-q[head])*Ap[i]);
while(head<=tail&&dp[i-W-1][q[tail]]-(j-q[tail])*Ap[i]<dp[i-W-1][j]) tail--;//如果更优
q[++tail]=j;
}
head=1;tail=0;
for(int j=mxp;j>=0;j--){
while(head<=tail&&q[head]-Bs[i]>j) head++;
if(q[head]>=j) dp[i][j]=max(dp[i][j],dp[i-W-1][q[head]]+(q[head]-j)*Bp[i]);
while(head<=tail&&dp[i-W-1][q[tail]]+(q[tail]-j)*Bp[i]<dp[i-W-1][j]) tail--;
q[++tail]=j;
}
}
ans=-inf;
for(int i=0;i<=mxp;i++)
ans=max(ans,dp[T][i]);
printf("%d\n",ans);
}
return 0;
}
四边形不等式优化DP
斜率优化DP
P3195 [HNOI2008] 玩具装箱
题目大意
传送门
P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为\(C_i\)。为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第\(i\)件玩具到第\(j\)个玩具放到一个容器中，那么容器的长度将为 \(x=j-i+Sigma(Ck)\)\(i \le K \le j\) 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为\(x\),其制作费用为\((X-L)^2\).其中\(L\)是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小。
\(1\le N \le 50000,1 \le L,C_i \le 10^7\)