P1020 【导弹拦截】(dilworth , lower_bound)
sdxjzsq
2018-07-22 03:01:35
### 姿势
1.Dilworth定理：
讲的比较专业的博客：[偏序集-Dilworth定理](https://blog.csdn.net/xuzengqiang/article/details/7266034)
一句话理解：
最长上升子序列的长度=划分成下降序列组数的最小值
推论：
最长下降子序列的长度=划分成上升序列组数的最小值
灵感来自：[学习笔记-Dilworth定理](https://blog.csdn.net/node_su/article/details/66041750)
一般来说运用Dilworth定理是用来计算最长上升子序列的长度，但这个题却是用最长上升子序列的长度来求划分成下降序列组数的最小值，实在是巧妙！
2.lower_bound和upper_bound的使用
lower_bound(g+1,g+n+1,val)-g是返回g[1..n]中第一个**大于等于**val的值的位置，而upper_bound(g+1,g+n+1,val)-g是返回g[1..n]中第一个**大于**val的值的位置。在本题中，前者用来求最长不降子序列，而后者用来求最长上升子序列。
3.
### code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001,inf=2147483647;
int a[maxn],g[maxn],f[maxn],n=0,maxx=0,tmp=0;
inline int rd()
{
char ch=getchar();int s=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s;
}
int main()
{
//freopen("a.in","r",stdin);
while(scanf("%d",&g[++n])!=EOF){}
n--;//cout<<'n'<<n<<endl;
for(int i=1;i<=n;i++)a[i]=g[i],f[i]=0,g[i]=inf;
for(int i=1;i<=n;i++)
{
f[i]=lower_bound(g+1,g+n+1,a[i])-g;
g[f[i]]=a[i];
tmp=max(tmp,f[i]);
}
//for(int i=1;i<=n;i++){cout<<a[i]<<endl;}
for(int i=1;i<=n;i++)g[n-i+1]=a[i],a[i]=inf,f[i]=0;
for(int i=1;i<=n;i++)
{
f[i]=upper_bound(a+1,a+n+1,g[i])-a;
a[f[i]]=g[i];
maxx=max(maxx,f[i]);
}
printf("%d\n%d",maxx,tmp);
}
```
### 题外话
今晚看完《工作细胞》刚更的第三集之后......又逛了一大圈，眼看又到了2:10......浪费了1.5h，唉~
其间看了《音乐少女》，其中女主一句话tm就直接改变N年未变的习惯，实在是夸张......得到的启示便是“**不要小看一句话的力量。有的时候，别人的一句话可能会造成很大的影响，它能让一个人恍然大悟**”。
另外工作细胞中的初始T细胞“活性化”也是十分感人的，而且，这惊人的再一次验证了“**不要小看一句话的力量。有的时候，别人的一句话可能会造成很大的影响，它能让一个人恍然大悟**”
真是神奇的巧合，所以，**在以后的生活中，应多说这种传递力量的话！！！也一定要善于倾听，从他人的话中汲取力量**！！！