一道经典dp题……

它有两问，第一问是一个裸的最长不上升子序列，不会的戳这里。至于第二问，非常简单，做法也有很多，像最长上升子序列、贪心、模拟…… 附一下代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff 

using namespace std;
int n,a[100005],sta[100005],t;
void two_fen(int k)
{
    int l = 1, r = t, mid;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(sta[mid] >= k) l = mid + 1;
        else r = mid - 1;
    }
    sta[l] = k;
}
void work()
{
    sta[0] = INF; t = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i] <= sta[t]) sta[++t] = a[i];
        else two_fen(a[i]);
    }
    //for(int i = 1; i <= t; i++) cout << sta[i] << “  “;cout <<endl;
    printf(“%d\n”,t);
}
void count()
{
    memset(sta,0,sizeof(sta));
    int j,place,x;
    t = 0;
    for(int i = 1; i <= n; i++)
    {
        place = 0; x = INF;
        for(int j = 1; j <= t; j++)
            if(sta[j] >= a[i] && (sta[j] < sta[place] || place == 0))
                place = j;
        if(place == 0) sta[++t] = a[i];
        else sta[place] = a[i];
    }
    printf(“%d\n”,t);
}
int main()
{
    while(cin >> a[++n]);
    n –;
    work();
    count();
    return 0;
}