AcWing 1016. 最大上升子序列和
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        for (int j = 1; j < i; j++)
            if (a[j]  < a[i])
                f[i] = max(f[i], f[j] + a[i]);
    }

    int res = 0;
    for (int i= 1; i <= n; i++) res = max(res, f[i]);

    printf("%d\n", res);

    return 0;
}
AcWing 1012. 友好城市
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII q[N];
int f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);  //按first进行排序

    int res=  0;
    for (int i = 0; i < n;i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (q[i].second > q[j].second)  //第一个点有序，第二点也要有序，否则两条桥梁就会交叉
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);        
    }

    printf("%d\n", res);

    return 0;
}
AcWing 1010. 拦截导弹
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main()
{
    while (cin >> q[n]) n++;

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int k = 0;   
        while (k < cnt && g[k] < q[i]) k++; //没有遍历完所有序列，当前序列的结尾是小于当前数的
        g[k] = q[i];
        if (k >= cnt) cnt++;
    }

    cout << cnt << endl;

    return 0;
}