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

这题其实还是挺裸的……但是为更加恶心的乱搞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;
}

• inline
• block