AcWing 1017. 怪盗基德的滑翔翼
不同点：这个题目并未说是从哪一端开始，因此需要判断两次——最长上升子序列与最长下降子序列（也可以在原有的基础上倒着算一遍也可以）

#include<iostream>
#include<cstring>

using namespace std;

const int N = 110;

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

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        cin >> n;
        for(int i=0;i<n;i++)cin >> h[i];

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

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

AcWing 1014. 登山
注意申清楚题意：首先先上山然后再下山，问在这个过程当中可以游玩的最大景点——相当于一个金字塔的形状
也就是求在i点，0~i的最长上升子序列，然后加上i+1~n的最长下降子序列
技巧：为了避免麻烦，首先预处理出来两边的最长上升子序列以及最长下降子序列，然后res=max(res,f[i]+d[i]-1)，之所以减去1，是因为i点重复算了两次

#include<iostream>

using namespace std;

const int N = 1010;

int f[N],d[N];
int n,h[N];

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)cin >> h[i];

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

    for(int i=n-1;i>=0;i--)
    {
        d[i]=1;
        for(int j=n-1;j>i;j--)
            if(h[i]>h[j])
                d[i]=max(d[i],d[j]+1);
    }

    int res=0;
    for(int i=0;i<n;i++)res=max(res,f[i]+d[i]-1);
    cout << res << endl;
    return 0;
}

AcWing 1016. 最大上升子序列和
在最长上升子序列中：f[i]表示的是以a[i]结尾的最长上升子序列的长度，在这里只需要将长度换为和即可
在初始化是也是类似的思路。

#include<iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)cin >> a[i];

    int res=0;
    for(int i=0;i<n;i++)
    {
        f[i]=a[i];
        for(int j=0;j<i;j++)
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+a[i]);
        res=max(res,f[i]);
    }
    cout << res << endl;
    return 0;
}

AcWing 1010. 拦截导弹
第一问求的是最长非上升子序列——注意审题，说的是不大于前一个炮弹的长度，因此需要加上等号
第二问：贪心的思路——类似于最长上升子序列的优化版
从第一个导弹开始，依次往后枚举，如果当前元素的值已经大于全部集合（一个系统里最小的那个尾值）里的元素了，那么此时需要再重新创建一个集合，同理依次枚举每一个元素。

#include<iostream>

using namespace std;

const int N = 1010;

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

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

    int res=0;
    for(int i=n-1;i>=0;i--)
    {
        f[i]=1;
        for(int j=n-1;j>i;j--)
            if(a[i]>=a[j])
                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&&d[k]<a[i])k++;
        //前一个判断指的是k并未超出集合，仍在枚举集合或者是集合里的所有数都小于当前数
        d[k]=a[i];//由于上一个循环已经结束——因此需要将当前数，放在集合里面
        if(k>=cnt)cnt++;
    }
    cout << cnt << endl;
    return 0;
}

AcWing 187. 导弹防御系统
与上一个题目类似，但是此时需要判断两种情况——上升与下降，两种情况所以在这里需要暴力把每一种情况都枚举一遍
dfs(i,j,k)——i:表示枚举到了哪一个点，如果枚举的点数已经与n相等，那么需要直接退出 ，防止继续枚举 j：表示上升子序列的集合个数 k：表示的是下降子序列的集合个数——开始的时候需要加答案初始化为n（就是一种特殊情况，集合元素全部相同）

#include<iostream>

using namespace std;

const int N = 60;

int up[N],down[N];
int n,a[N];
int ans;

void dfs(int u,int su,int sd)
{
    if(su+sd>=ans)return ;
    if(u==n)
    {
        ans=min(ans,su+sd);
        return ;
    }

    int k=0;
    while(k<su&&up[k]>=a[u])k++;
    if(k<su)
    {
        int t=up[k];
        up[k]=a[u];
        dfs(u+1,su,sd);
        up[k]=t;
    }
    else 
    {
        up[k]=a[u];
        dfs(u+1,su+1,sd);
    }

    k=0;
    while(k<sd&&down[k]<=a[u])k++;
    if(k<sd)
    {
        int t=down[k];
        down[k]=a[u];
        dfs(u+1,su,sd);
        down[k]=t;
    }
    else 
    {
        down[k]=a[u];
        dfs(u+1,su,sd+1);
    }

}

int main()
{
    while(cin >> n,n)
    {
        ans=n;
        for(int i=0;i<n;i++)cin >> a[i];
        dfs(0,0,0);
        cout << ans << endl;
    }
    return 0;
}

AcWing 272. 最长公共上升子序列
f[i][j]表示的是以b[j]为结尾的最长公共上升子序列
通常这种情况都是直接枚举包不包含a[i]这个元素来分类讨论
如果不选a[i]的话，f[i][j]=f[i-1][j]
如果选的话，说明a[i]==b[j],不然的话情况就会和不选的时候一样

最暴力的写法

#include<iostream>

using namespace std;

const int N = 3010;

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

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<=n;i++)cin >> b[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])
            {
                f[i][j]=max(f[i][j],1);
                for(int k=1;k<j;k++)
                    if(b[j]>b[k])f[i][j]=max(f[i][j],f[i][k]+1);
            }
        }
/*
优化：
for(int i=1;i<=n;i++)
    {
        int maxv=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])f[i][j]=max(f[i][j],maxv);
            if(b[j]<a[i])maxv=max(maxv,f[i-1][j]+1);
        }
    }
*/
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[n][i]);
    cout << res << endl;
}