P1020 导弹拦截

• 前面

参考博客：Dilworth定理 Dilworth定理是个啥东东

的代码：P1020 导弹拦截 能过50%

对于STL中 二分查找的函数，自定义cmp：题解 P1020 【导弹拦截】

对于LIS的写法：O(NlogN)做法：贪心+二分

---

没想到，本来以为是个简单的DP，咋整来这么多知识？？

---

• 题目描述 

题目就是

①先求最长的，非上升的，子序列的长度

②求这样的子序列 有几个，根据那什么定理，就是求出来最长的，上升的子序列长度。

这个什么定理：偏序集能划分成的最少的全序集个数等于最大反链的元素个数。

偏序关系是 >=，全序集的个数（最长的非上升子序列的个数）== 最大反链（最长的上升子序列）的长度 

---

• 两种方法

最长的非上升子序列长度，最长的上升子序列长度，是同样的思路。

的思想是动态规划。

的思想是 贪心+二分。

---

• 动态规划

动态规划的思想，简单说来。

// 50 %
//P1020

const int maxn=1e5+5;
int num[maxn];
int dp[maxn];

int main()
{
	int ii=1;
	while(scanf("%d",&num[ii])!=EOF)
		ii++;
	ii--;
	int len=ii;
	
	for(int i=1;i<=len;i++)
		dp[i]=1;
		
	for(int i=2;i<=len;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(num[j]>=num[i])
				dp[i]=max(dp[i],dp[j]+1);
		}

	}
	
	int ans1=0;
	for(int i=1;i<=len;i++)
	{
	//	cout<<dp[i]<<" ";
		ans1=max(ans1,dp[i]);
	}
	cout<<ans1<<endl;
	
	for(int i=1;i<=len;i++)
		dp[i]=1;
	for(int i=2;i<=len;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(num[j]<num[i])
				dp[i]=max(dp[i],dp[j]+1);
		}
	}
	int ans2=0;
	for(int i=1;i<=len;i++)
	{
	//	cout<<dp[i]<<" ";
		ans2=max(ans2,dp[i]);
	}
	cout<<ans2<<endl;
	
}

以非上升序列为例： 数组表示 以第  个元素作为结尾，最长的非上升序列的长度。

所以，初始化全部为1。

递推关系式为：。

说明 包含第  个元素的长度，是由前面的，某个长度推来的。（满足条件emmm），大概这个意思。

最后要注意的是，需要循环遍历 数组，找到最大值。这是因为的定义，但是最长的长度并不一定包含了最后一个元素，并不一定是.

---

• 贪心+二分

表示表示长度为  的LIS结尾元素的最小值。 
利用贪心的思想，对于一个上升子序列，显然当前最后一个元素越小，越有利于添加新的元素，这样LIS长度自然更长。 

就是这个博客，讲的肥肠好

 如果你不想写二分的代码，你可以使用自带的STL函数。但是由于upper_bound函数，要求是递增序列，我们在求最长的非上升子序列长度时，dp数组的必然是非递增序列，所以需要重新定义函数，

这里的greater<int>()就是c++友情提供的方便的大于函数，这样就不用自己动手写一个cmp函数了(雾).

const int maxn=1e5+5;
int num[maxn];
int dp[maxn];

int main()
{
	int ii=1;
	while(scanf("%d",&num[ii])!=EOF)
		ii++;
	ii--;
	int len=ii;
	
	
	int pos=1;
	dp[1]=num[1];
	for(int i=2;i<=len;i++)
	{
		if(num[i]<=dp[pos])
		{
			dp[++pos]=num[i];
		}
		else
			dp[upper_bound(dp+1,dp+pos+2,num[i],greater<int>() )-dp]=num[i];
	}
	cout<<pos<<endl;
	
	//最长上升子序列 
	for(int i=1;i<=len;i++)
		dp[i]=9999999;
	pos=0;
	dp[1]=num[1];
	for(int i=2;i<=len;i++)
	{
		if(num[i]>dp[pos])
		{
			dp[++pos]=num[i];
		}
		else
			dp[lower_bound(dp+1,dp+pos+2,num[i])-dp]=num[i];
	}
	cout<<pos<<endl;
	
}