LIS,Dilworth定理

题意:

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入描述:
1行，若干个整数（个数≤100000）
输出描述:
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

分析：

很明显两个问题
第一个就是求最长的不上升子序列的长度。
第二个是求原序列最少可划分为多少不上升子序列

第一个暂时搁浅，我们看第二个，根据dilworth定理我们知道可划分的最少不上升子序列的数目就是其最长下降子序列的长度。具体证明见百度百科，里用数学归纳法证明的。

我们专心来看第一个问题：
如何求最长的不上升子序列的长度，其实这和转化后的第二个问题一样了。

这是典型的LIS问题(Longest Incresing Sub-sequence)，最长上升子序列问题
有三种解决办法：O(n^2)的动态规划，O(nlogn)的贪心和动态规划，O(nlogn)的用树状数组优化后的动态规划

1.O(n^2)的动态规划：
我们定义d[i]为到i为止且以in[i]为末端的最长的上升子序列的长度。
转移方程很简单，我们到i的前面去找in[j]<in[i]的j，然后尝试再d[j]后加上in[i]
即dp[i] = max(d[j] for j in range(1,i) if in[j] < in[i])+1
很明显这是需要O(n^2)的时间开销。

2.O(nlogn)的二分加贪心
给出贪心策略：对于相同长度的子序列他的最后的一个元素的值越小
那么我们越有可能在后面的遍历中给它加上其他元素
即，对于长度为k的子序列我们在不断遍历中维护其最后一位的最小值。

用一个数组low[i]表示：长度为i的子序列的末端最小值。
我们维护low
我们遍历每一个a[i]时都到low去比较，如果low[j]<a[i]
那么a[i]可以放在长度为j的子序列的后面即此刻low[i+1]可能更新
我们看low[i+1]是否比a[i]大如果low[i+1]>a[i]那么low[i+1]=a[i]
但如果这样的话，我们仍是O(n^2)的时间开销

现在我说，low一定是单调不下降的！low[j+1]>=low[j]
即目前所遍历的序列s[0:i]中长度为j的上升子序列的末端一定小于长度为j+1的上升子序列的末端
这是显然易见的，因为长度为j+1的上升子序列就包括长度为j的上升子序列啊

那么我们再看，什么时候low[j+1]会更新:当a[i]>a[j]且a[i]<a[j+1]时！
结合low是个从小到大的有序序列，我们可以轻易地发现这是二分查找！！
即C++里的lower_bound(序列中的第一个大于等于target的位置)
如果求的不是最长上升子序列而是最长不下降子序列的话就用upper_bound了
因为此时的条件是a[i]>=a[j]且a[i]<a[j]了

如果是下降子序列，只需将原数组到换过来就好了
如此操作，我们形成了O(nlogn)的算法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int max_n = 1e5 + 100;
const int inf = 30010;
int low[max_n];
int missile[max_n];
string s;

int main() {
    ios::sync_with_stdio(0);
    int n = 0;int ans1, ans2;
    while (cin >> missile[n])n++;
    fill(low, low + n, inf);
    for (int i = 0;i < n;i++) {
        int idx = lower_bound(low, low + n, missile[i]) - low;
        low[idx] = missile[i];
    }
    for (int i = n - 1;i >= 0;i--)
        if (low[i] != inf) {
            ans2 = i + 1;
            break;
        }
    reverse(missile, missile + n);
    fill(low, low + n, inf);
    for (int i = 0;i < n;i++) {
        int idx = upper_bound(low, low + n, missile[i]) - low;
        low[idx] = missile[i];
    }
    for (int i = n - 1;i >= 0;i--)
        if (low[i] != inf) {
            ans1 = i + 1;
            break;
        }
    cout << ans1 << endl << ans2 << endl;
}

3.树状数组dp优化
还不会树状数组，会了更新。。。。。。

拦截导弹

LIS,Dilworth定理

题意:

分析：