拦截导弹 题解
拦截导弹
https://ac.nowcoder.com/acm/problem/16810
本题要求的是一个最大不增子序列长度和一个最大递增子序列的长度。
关于这两个问题的求解，过于经典不再赘述。
问题的关键是第二个问题是如何转化而来的。
第二个问题是通过Dilworth定理得到的。
引入两个离散数学的概念：
链（chain）是一个偏序集S的全序子集（所谓全序是指任意两个元素可比较）
反链（antichain）是一个偏序集S的子集，其中任意两个元素不可比较.
dilworth说的是:最大链的长度等于最少反链覆盖数.而最大反链的长度等于最少链覆盖数.
离散数学中有一个知识点叫作二元关系，所谓二元关系通俗的理解就是某一个元素有两个键值，用以下的代码来简单的理解一下
struct node{inta,b;}bool operator < (node n1,node n2){return n1.a<n2.a&&n1.b<n2.b;}
在以上例子中，只有一个对象的a,b均小于另一个对象，两者才可比。
那么在一个序列中，我们将一个元素的值记作a，所在的位置记作b。
那么当且仅当位置靠左的元素小于位置靠右的元素的时候，这两者才可比。
所以在这里一个最长的链，就是最长递增子序列
同理，当位置靠左的元素不小于位置靠右的元素时，满足n1.b<n2.b但是不满足n1.a<n2.a
两者不可比较，反链要求其中任意两个元素均不可比较，那么最长的反链就是最长不增子序列。
再运用dilworth定理，我们便可以得到，最大不增子序列的覆盖数就等于最长递增子序列的长度
那么在一个序列中，我们将一个元素的值记作a，所在的位置记作b。
那么当且仅当位置靠左的元素小于位置靠右的元素的时候，这两者才可比。
所以在这里一个最长的链，就是最长递增子序列
同理，当位置靠左的元素不小于位置靠右的元素时，满足n1.b<n2.b但是不满足n1.a<n2.a
两者不可比较，反链要求其中任意两个元素均不可比较，那么最长的反链就是最长不增子序列。
再运用dilworth定理，我们便可以得到，最大不增子序列的覆盖数就等于最长递增子序列的长度
#include <bits/stdc++.h>
using namespace std;
int a[100100];
int L[100100];
int main()
{
int tmp;
int n=0;
while(scanf("%d",&tmp)!=EOF)
{
a[++n]=tmp;
}
int len=0;
for(int i=n;i>=1;i--)
{
if(len==0)
L[++len]=a[i];
else if(a[i]>=L[len])
L[++len]=a[i];
else
{
int p=upper_bound(L+1,L+1+len,a[i])-L;
L[p]=a[i];
}
}
printf("%d\n",len);
len=0;
memset(L,0,sizeof(L));
for(int i=1;i<=n;i++)
{
if(len==0)
L[++len]=a[i];
else if(a[i]>L[len])
L[++len]=a[i];
else
{
int p=lower_bound(L+1,L+1+len,a[i])-L;
L[p]=a[i];
}
}
printf("%d\n",len);
} 
