单调队列优化
眼界极窄的ZZ之前甚至不会单调队列……（好丢人啊）
单调队列优化的常见情景：
- 转移可以转化成只需要确定一个维度，而且这个维度的取值范围在某个区间里
修剪草坪
这个题学长讲的好像是另外一个思路，但是码的时候不知不觉就偏到另一个思路里去了……改天也打打试试
需要注意的：
- 这题中如果有多个满足最大值，我们应该取最靠前的，所以在弹队的时候用的是
> - 这个题中单调队列维护的是(dp_{j,0}-pre_j(i-k-1leq j leq i))，这里的(j)是入队时的下标
精华：
for(int i=1;i<=n;i++)
{
dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
while(fro<=bac&&Q[fro].id+k+1<=i)fro++;
//ll t=Q[fro].id;
dp[i][1]=Q[fro].v+pre[i];
while(fro<=bac&&dp[i][0]-pre[i]>Q[bac].v)bac--;
Q[++bac].v=dp[i][0]-pre[i];
Q[bac].id=i;
}
股票交易
这道题和上一道的特征很是不同……
- 如果多个满足最大值，这个题里不需要选最靠前的，所以弹队的时候用的是
≥ - 这个题中单调队列维护的是（以买入举例，卖出同理）(dp_{i-w-1,k}+kcdot ap_i)，而这里的(i)是每循环都会更新的，所以就不能偷懒在入队时算好了
- 手里没股票也是一种情况，所以算什么的时候都不要忘了考虑(j=0)的情况。
（突然发现自己之前一直都在用一种诡异的结构体写法）
精华：
for(int i=1;i<=t;i++)
{
for(int j=0;j<=as[i];j++)dp[i][j]=-j*ap[i];
for(int j=0;j<=mp;j++)dp[i][j]=max(dp[i][j],dp[i-1][j]);//nothing
if(i-w-1<0)continue;
fro=1;bac=0;
for(int j=0;j<=mp;j++)//buy
{
while(fro<=bac&&Q[fro]<j-as[i])fro++;
while(fro<=bac&&dp[i-w-1][j]+ap[i]*j>=dp[i-w-1][Q[bac]]+ap[i]*Q[bac])bac--;
Q[++bac]=j;
if(fro<=bac)dp[i][j]=max(dp[i][j],dp[i-w-1][Q[fro]]+ap[i]*Q[fro]-j*ap[i]);
}
fro=1;bac=0;
for(int j=mp;j>=0;j--)
{
while(fro<=bac&&Q[fro]>j+bs[i])fro++;
while(fro<=bac&&dp[i-w-1][j]+bp[i]*j>=dp[i-w-1][Q[bac]]+bp[i]*Q[bac])bac--;
Q[++bac]=j;
if(fro<=bac)dp[i][j]=max(dp[i][j],dp[i-w-1][Q[fro]]+bp[i]*Q[fro]-j*bp[i]);
}
}
瑰丽华尔兹
首先发现如果按每一个时刻设方程是(O(n^3))的，会炸得很惨，
然后想到对每一个时间段列方程，因为时间段长度一定，所以发现出现了一个能够转移的区间，就可以考虑单调队列优化。
设从((x',y'))走到((x,y))，则有转移方程：(dp[x][y]=dp[x'][y']+dis)
然后把所有可以转移的用单调队列优化下即可，其他判边界啥的就是基本操作了
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define N 205
#define ll long long
ll dp[N][N]={0};
ll dx[5]={0,-1,1,0,0};
ll dy[5]={0,0,0,-1,1};
struct QUE
{
ll v,id;
}Q[N];
ll f,b;
ll n,m,x,y,k;
ll s,t,d;
ll mp[N][N];
ll ch;
ll ans=0;
void doit(ll sx,ll sy,ll dis,ll dir)
{
f=1;b=0;
for(int i=1;1<=sx&&sx<=n&&1<=sy&&sy<=m;sx+=dx[dir],sy+=dy[dir],i++)
{
//cout<<sx<<' '<<sy<<endl;
if(!mp[sx][sy]){f=1;b=0;continue;}
while(f<=b&&Q[f].id+dis<i)f++;
while(f<=b&&dp[sx][sy]>Q[b].v+i-Q[b].id)b--;
Q[++b]=(QUE){dp[sx][sy],i};
dp[sx][sy]=Q[f].v+i-Q[f].id;
//cout<<dp[sx][sy]<<endl;
}
}
int main()
{
cin>>n>>m>>x>>y>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
do ch=getchar(); while(ch!='.'&&ch!='x');
ch=='.'?mp[i][j]=1:mp[i][j]=0;
}
}
memset(dp,128,sizeof(dp));
dp[x][y]=0;
for(int i=1;i<=k;i++)
{
cin>>s>>t>>d;
if(d==1)for(int j=1;j<=m;j++)doit(n,j,t-s+1,d);
else if(d==2)for(int j=1;j<=m;j++)doit(1,j,t-s+1,d);
else if(d==3)for(int j=1;j<=n;j++)doit(j,m,t-s+1,d);
else if(d==4)for(int j=1;j<=n;j++)doit(j,1,t-s+1,d);
}
ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//cout<<dp[i][j]<<' ';
ans=max(ans,dp[i][j]);
}
//cout<<endl;
}
cout<<ans;
return 0;
}
诗人小G
这题首先要证明决策单调性，然而我根本不会四边形不等式，只能猜结论蒙过，所以先留坑，各位可以先看洛谷一位神仙的证明
主要思路就是单调队列存决策和他使用的范围，每次进队二分出新决策的范围，然后把劣质决策(pop)掉，然后每个决策拉一个指针指到上一个决策也就是当前队头
还有就是输出是真的恶心
我的天哪我都在讲些什么……总之这题需要一些理解时间，我水平有限只能写成这样了……大家还是多多思考吧QAQ