2442: [Usaco2011 Open]修剪草坪 - #include <Seter> - using namespace Orz;

2442: [Usaco2011 Open]修剪草坪

Seter posted @ 2011年8月27日 14:00 in BZOJ with tags DP usaco , 2761 阅读

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
147227	Seter	2442	Accepted	1928 kb	88 ms	C/Edit	648 B	2011-08-27 13:53:40

在jiangzoi神犇的提示下随便写了一个居然TIME就R1了……RP好……希望RP好到能帮我做完作业……

看到这题一开始肯定会想到直接DP。f[i]表示选第i头牛的最大代价，f[i]=max(f[j]+a[j+2]+a[j+3]+...+a[i])这样转移……貌似可以优化到O(nlgn)？反正不行的话把所有牛掉个个儿应该也能过。

但是作为一个蒟蒻当然要想更简单的方法……便便告诉我们正难则反……于是反过来考虑。f[i]表示不选第i头牛的最小代价，结果会发现：f[i]=min(f[j])+a[i]！于是可以单调队列O(n)水过，trick是一开始和最后分别加个0。

2442
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	`#include <stdio.h>` `struct` `pair{int` `i;long` `long` `e;}que[100002];` `int` `bq=0,eq=1,n,k;` `inline` `getint(){` `int` `re=0,ch=getchar(),k;` `while(ch!='-'&&(ch<'0'\|\|ch>'9'))if((ch=getchar())<=0)return` `-1;` `for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;` `return` `k?-re:re;` `}main(){` `long` `long` `sum=0,t;` `int` `i;n=getint();k=getint()+1;que[0].i=-1;` `for(i=0;i<n;i++){` `if(que[bq].i+k<i)bq++;` `sum+=(t=getint());t+=que[bq].e;` `while(bq!=eq&&que[eq-1].e>=t)eq--;` `que[eq].e=t;que[eq++].i=i;` `}if(que[bq].i+k<i)bq++;` `printf("%lld\n",sum-que[bq].e);` `return` `0;` `}`

By Seter