dp与贪心解LIS问题

1、dp + dp

O(n^2)
第一问显然每套导弹拦截系统拦截导弹高度为不升子序列，求最长的就好了
第二问求导弹拦截系统的个数可以转化为求最长上升子序列长度
证明见： Tian-Xing’s blog orz orz

1、首先我们把这些导弹分为s组（s即为所求答案）
可以看出每一组都是一个不升子序列
2、划分完后我们在组一里找一个原序列里以组一的开头点连续的不升子串的最后一个元素，可以知道在组2中一定有一个大与它的点
（如果组二中没有的话，那么组二中最高的导弹高度必然小于这个点，而其他的高度都小于这个高度而且是递减或相等的，那么没有必要再开一个组二了，矛盾，所以不存在找不到比他大的点的情况）
3、以此类推，对于每一个k组（1<=k<n）都可以找到这样的一些点
所以把这些点连起来，就是一条上升子序列。
4、设最长上升子序列长度为l
所求上升子序列为h
那么h<=l
因为最长上升子序列任意两个不在一组内
(如果在同一个组内，则每个组的数不成为一个不生子序列，矛盾）
所以l==h

比较难理解
我们来看组数据
389 207 155 300 299 170 158 65
组一 389 207 155 65 组二 300 299 170 158
步骤一中我们一开始找到的点是1
因为如果找65不好解释，所以我们找原数列里连续的最后一个即155
组二里可以找到300比他大
所以最长上升子序列长度为2==答案

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 1005;
int n, a[maxn];
int f[maxn], g[maxn];

int main()
{
    while(cin >> a[n]) n ++;
    int ans1 = 0;
    int ans2 = 0;
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        g[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
            else g[i] = max(g[i], g[j] + 1);
        }
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    cout << ans1 << endl;
    cout << ans2 << endl;
    return 0;
}

2、dp + 贪心

O(n^2)

题目的第二问，对于第i号导弹，要么选择末尾导弹高度最小的拦截系统，要么新创一个拦截系统，用一个数字即每套拦截系统此时所拦截的最后一个导弹高度，来表示该系统。
这样就得到了一个数组，数组最终长度就是所需最少拦截系统数目。

int main()
{
    while(cin >> a[n]) n ++;
    int ans = 0, cnt = 0;
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
        {
            if(a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
        //数组g的每个元素代表一套导弹拦截系统的拦截序列
        //g[i]表示此时第i套导弹拦截系统所拦截的最后一个导弹的高度
        int p = lower_bound(g, g+cnt, a[i]) - g;
        if(p == cnt) g[cnt ++] = a[i];  //a[i]开创一套新拦截系统    
        else g[p] = a[i];               //a[i]成为第p套拦截系统最后一个导弹高度
    }
    cout << ans << endl;
    cout << cnt << endl;
    return 0;
}

3、贪心 + 贪心

O(nlogn)

int main()
{
    //cnt表示导弹系统数，len表示一个系统最多能拦截的导弹数
    int len = 0, cnt = 0;
    int a;
    while(cin >> a)
    {
        //pos1表示以a结尾的最长不升子序列长度
        int pos1 = upper_bound(f, f+len, a, greater<int>()) - f;
        if(pos1 == len) f[len ++] = a;
        else f[pos1] = a;

        int pos2 = lower_bound(g, g+cnt, a[i]) - g;
        if(pos2 == cnt) g[cnt ++] = a;
        else g[pos2] = a;
    }
    cout << len << endl;
    cout << cnt << endl;
    return 0;
}

upper_bound与lower_bound 傻傻分不清楚

cpp reference

• lower_bound
• upper_bound

若数组升序排列
lower_bound(begin, end, a) 返回数组[begin, end)之间第一个大于或等于a的地址，找不到返回end （可以等于所以low）
upper_bound(begin, end, a) 返回数组[begin, end)之间第一个大于a的地址，找不到返回end （一定大于所以up）

若数组降序排列，可写上比较函数greater<type>()
lower_bound(begin, end, a, greater<int>()) 返回数组[begin, end)之间第一个小于或等于a的地址，找不到返回end
upper_bound(begin, end, a, greater<int>()) 返回数组[begin, end)之间第一个小于a的地址，找不到返回end

非数值数组的情况可选择手写比较函数，如

bool cmp(node a, node b)
{
    if(a.value1 != b.value1) return a.value1 < b.value1;
    else return a.value2 < b.value2;
}