CODEVS 1576 && COGS 1398 && Openjudge 1759 最长上升子序列

改了半天,总算把严格A掉了

d[i] = lower_bound(S, S+i, a[i]) - S; 
S[d[i]] = min(S[d[i]], a[i]);
ans = max(ans, d[i]+1);

d[i] = upper_bound(S, S+i, a[i]) - S; 
S[d[i]] = min(S[d[i]], a[i]);
ans = max(ans, d[i]);

不上升什么的。。。全部取相反数就好了2333333333

不得不说这个模板真是太方便了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define for0(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
using namespace std;
int n,ans,a[30010],d[30010],S[30010];
#define INF 0x7fffffff
void init()
{
	for0(i,n) S[i] = INF;
	memset(d, 0, sizeof(d));
}
int main()
{
	scanf("%d",&n);
	for0(i,n)scanf("%d",&a[i]);
	init();
	for0(i,n){
		d[i] = lower_bound(S, S+i, a[i]) - S; 
		S[d[i]] = min(S[d[i]], a[i]);
		ans = max(ans, d[i]+1);
	}
	cout<<ans<<endl;
}

———————————————2016.06.15分割线—————————————————————

辣鸡CV,只测样例(((

你说我一个错误的代码,怎么就AC了呢。。。。。

S[d[i] = lower_bound(S, S+i, a[i]-1) - S;] = min(S[d[i]], a[i]);
ans = max(ans, d[i]);

此条目发表在CODEVS, DP, LIS, OpenJudge, 线形DP分类目录。将固定链接加入收藏夹。