首页 > 代码库 > BZOJ 2442: [Usaco2011 Open]修剪草坪
BZOJ 2442: [Usaco2011 Open]修剪草坪
Description
在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，那么，这些奶牛就会罢工去开派对:)。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。
Input
* 第一行：空格隔开的两个整数N和K
* 第二到N+1行：第i+1行有一个整数E_i
Output
* 第一行：一个值，表示FJ可以得到的最大的效率值。
题解：
定义F[i]为前 i-1 只奶牛工作效率的最大值。
sum[i]是Ei的前缀和。
有F[i]=max{F[j]+sum[i-1]-sum[j]} (i-j<k)
可以用单调队列维护 F[j]-sum[j] 。
代码：
#include<cstdio>using namespace std;long long sum[100005];long long f[100005];long long n,k;struct N{ int x;long long w; N(int a=0,long long b=0){ x=a,w=b; }};struct dddl{ int h,t; N q[100005]; void insert(N a){ while(h!=t&&q[t-1].w<=a.w) t--; q[t++]=a; } void pop(int x){ if(q[h].x==x) h++; } long long ask(){ return q[h].w; }}dddl;int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&sum[i]); } k++; for(int i=1;i<=n;i++) sum[i]+=sum[i-1]; dddl.insert(N(0,0)); for(int i=1;i<=n+1;i++){ dddl.pop(i-k-1); f[i]=dddl.ask()+sum[i-1]; dddl.insert(N(i,f[i]-sum[i])); } printf("%lld\n",f[n+1]); return 0;}
BZOJ 2442: [Usaco2011 Open]修剪草坪
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。