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

2442: [Usaco2011 Open]修剪草坪

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

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

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee