51nod P3111 小明爱拦截【树状数组】【DP】

这道题就是拦截导弹
然后可以用树状数组优化
拦截导弹的本质就是求最长不上升子序列。
然后把求最长不下降序列的数组倒过来求就好了。

#include
#include
#include
using namespace std;
long long n,ans,c[2000020];
long long f[2000020];
pair  a[2000020];
void insert(long long x,long long y)
{
	while(x<=200020)
	 {
	    c[x]=max(c[x],y);
	    x+=(x&-x);
	 }
}
long long query(long long x)
{
	long long maxn=0;
	while(x)
     {
     	maxn=max(maxn,c[x]);
     	x-=(x&-x);
	 }
	return maxn;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)
	 {
	   scanf("%lld",&a[n-i+1].first);
	   a[n-i+1].second=n-i+1;
	 }
	sort(a+1,a+1+n);
	for(int i=1; i<=n; i++)
	 {
	   f[i]=query(a[i].second)+1;
	   insert(a[i].second,f[i]);
	 }
	for(int i=1; i<=n; i++)
	   ans=max(ans,f[i]);
	printf("%lld",ans);
	return 0;
}