bzoj2442&&codevs4654 单调队列优化dp

这道题也是一道单调队列 很明显满足各种性质 f【i】表示i不选前面k-1个都选的最小损失 维护的是个单增队列 q【head】是队列最小值 代码十分简介 注意longlong就okay

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define inf 99999999999999LL
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
LL ans,mn=inf,f[M];
int w[M],head,tail,k,n;
struct node{int pos; LL v;}q[M];f
int main()
{
n=read(); k=read();
for(int i=;i<=n;i++) w[i]=read(),ans+=w[i];
for(int i=;i<=n;i++){
f[i]=q[head].v+w[i];
while(head<=tail&&q[tail].v>f[i]) tail--;
q[++tail].v=f[i]; q[tail].pos=i;
while(head<=tail&&q[head].pos<i-k) head++;
}
for(int i=n-k;i<=n;i++) mn=min(mn,f[i]);
printf("%lld\n",ans-mn);
return ;
}
上一篇:【JAVA笔记】JAVA后端实现统一扫码支付:微信篇


下一篇:FM算法(二):工程实现