拦截导弹

贪心找最大上升子序列个数

原理

再维护一个数组，存放每组下降(上升)序列的结尾的值，
如果现有的子序列的结尾都小于当前数，则创建新子序列
将当前数放到结尾大于等于它的最小的子序列后面

#include <iostream>

using namespace std;

const int N=100010;
int a[N],f[N];
int g[N];

int main()
{
    int n=1;
    while(cin>>a[n])
    {
        n++;
    }

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



    int num=0;
    for(int i=1;i<=n;i++)
    {
        int k=0;
        //a[i]大，k就继续往后找，a[i]小了，就直接停住
        while(k<num && g[k]<a[i])
        {
            k++;
        }
        g[k]=a[i];
        if(k>=num)
        num++;
    }
    cout<<cnt<<endl<<num;
    return 0;
}

2023/11/25

前半段是最长上升子序列
后半段和dp无关，是贪心，没想出来。需要复习:
再维护一个数组，存放每组下降(上升)序列的结尾的值，
如果现有的子序列的结尾都小于当前数，则创建新子序列
将当前数放到结尾大于等于它的最小的子序列后面

#include <iostream>

using namespace std;

const int N=100010;
int a[N],f[N];
int g[N];

int main()
{
    int n=1;
    while(cin>>a[n])
    {
        n++;
    }

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



    int num=0;
    for(int i=1;i<=n;i++)
    {
        int k=0;
        //a[i]大，k就继续往后找，a[i]小了，就直接停住
        while(k<num && g[k]<a[i])
        {
            k++;
        }
        g[k]=a[i];
        if(k>=num)
        num++;
    }
    cout<<cnt<<endl<<num;
    return 0;
}