当有形如\(f_i=min_{j=0}^{l(i)}f_j+w转移代价\)
我们就可以使用单调栈优化DP
为什么不用单调队列???
当有形如\(f_i=min_{j=l(i)}^{i-1}f_j+w转移代价\)
我们就可以使用单调队列优化DP
至于为毛,就可以从它的工作原理上去分析
6305. 最小值
\(dp_i=min_{j=0}^{i-1}g_j+f(min_{x=j+1}^{i}a_x)\)
然后用单调栈转移
#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=(a);i<=(b);i++)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,x[200005],ls[200005],top;
long long f[200005],g[200005],mx[200005],a,b,c,d;
struct node{
long long t;
int xx;
}q[200005];
int main(){
fre(min);
scanf("%d%lld%lld%lld%lld",&n,&a,&b,&c,&d);
Fu(i,1,n) scanf("%d",&x[i]),f[i]=a*x[i]*x[i]*x[i]+b*x[i]*x[i]+c*x[i]+d;;
Fu(i,1,n){
long long o=g[i-1];
while(top&&x[q[top].xx]>=x[i]) o=max(o,q[top].t),top--;
g[i]=o+f[i];
if(top) g[i]=max(g[i],g[q[top].xx]);
q[++top].t=o,q[top].xx=i;
}
printf("%lld",g[n]);
return 0;
}
标签:min,top,xx,DP,优化,单调
From: https://www.cnblogs.com/zhy114514/p/18028150