首页 > 代码库 > bzoj2442&&codevs4654 单调队列优化dp
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=100007; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); 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=1;i<=n;i++) w[i]=read(),ans+=w[i]; for(int i=1;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 0; }
bzoj2442&&codevs4654 单调队列优化dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。