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

1052: [HAOI2007]覆盖问题

2442: [Usaco2011 Open]修剪草坪

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

http://www.zybbs.org/JudgeOnline/problem.php?id=2442

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。

#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

inline
block