1109: [POI2007]堆积木Klo - #include <Seter> - using namespace Orz;

1109: [POI2007]堆积木Klo

Seter posted @ 2012年2月10日 00:18 in BZOJ with tags DP POI , 2741 阅读

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

RunID User Problem Result Memory Time Language Code Length Submit Time
201611 Seter 1109 Accepted 2952 kb 156 ms C++/Edit 714 B 2012-02-09 19:26:14

这题其实还是挺裸的……但是为更加恶心的乱搞DP题提供了一点基础……

不过我现在想得是:快点写完题解去补作业去了囧……

先列下DP方程。令f[i]是第i个积木在自己的位置上时,前i个积木中最多能归位的数目。

f[i]=max{f[j]|i>j,a[i]>a[j],a[i]-a[j]<=i-j}+1

其中a[i]>a[j]是保证i,j都在自己的位置上,a[i]-a[j]<=i-j是为了保证中间有足够的积木让i能在a[i]这个位置上。

为了让每个限制只和位置有关,a[i]-a[j]<=i-j可以变形为a[i]-i<=a[j]-j。

这样一弄,好像就是一个LIS嘛!

问题来了,这个东西有两个变量,难道要像LIS2那样乱搞?

我们将下面两个式子加起来,

1:a[i]-i<=a[j]-j ===> -a[i]+i>=-a[j]+j

2:                                  a[i]>a[j]

得到i>j……说明只要满足a[i]>a[j]和a[i]-i<=a[j]-j,则一定满足i>j!

那么就只要按照a[i]-i排序(你想按照a[i]排序也行,那样两数相等就在求LIS的时候判了),求LIS即可。

由于a[i]-i相等时,a[i]升序就可以使答案最大化,所以排序的时候第二关键字要弄成a[i]。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
int n,s,q[100000],k;
char str[1000000],*p=str;
pair<int,int>a[100000];
inline int getint(){
	int re=0;
	while(!isdigit(*p))p++;
	while(isdigit(*p))re=re*10+*p++-48;
	return re;
}int main(){
	int i=0,l,r,mid;fread(p,1,1000000,stdin);
	for(n=getint();i++!=n;)if((r=getint())<=i)a[s].first=i-(a[s].second=r),s++;
	sort(a,a+s);
	for(i=-1;++i!=s;){
#define x a[i].second
		if(!k||q[k-1]<x){q[k++]=x;continue;}
		l=-1;r=k-1;
		while(l+1!=r)if(q[mid=l+r+1>>1]<x)l=mid;else if(q[mid]!=x)r=mid;else{r=mid;break;}
		if(q[r]!=x)q[r]=x;
	}printf("%d\n",k);
	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