最长上升子序列模型

题谱如上：

也是一些可以套模版来做的。

就是遍历前面已经扫描的点的状态，找出一个最大的，使用它来表示当前状态。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;

int k;

int main()
{
    scanf("%d", &k);
    while (k--)
    {
        int n;
        // 记录楼的高度
        int h[N];
        // 记录到第i栋楼的最大跳跃次数
        int f[N];
        // 记录最大值,切记要初始化(已老实)
        int ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf(" %d", &h[i]);

        // 正向遍历求最大值
        for (int i = 1; i <= n; i++)
        {
            f[i] = 1;
            for (int j = 1; j < i; j++)
            {
                if (h[i] < h[j])
                {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            ans = max(ans, f[i]);
        }

        // 反向遍历求最大值
        for (int i = n; i >= 1; i--)
        {
            f[i] = 1;
            for (int j = n; j > i; j--)
            {
                if (h[i] < h[j])
                {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            ans = max(ans, f[i]);
        }

        printf("%d\n", ans);
    }

    return 0;
}

1014. 登山 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;

int n;
// 记录海拔
int h[N];
// f[i]表示上山上到第i个景点,爬的最多的山的数量
// b[i]表示下山从第i个景点,走过的最多的山的数量
int f[N], b[N];

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

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

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

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

    printf("%d", ans);
    return 0;
}

482. 合唱队形 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;

// 其实就是最少的不爬的山的数量

int n;
// 记录海拔
int h[N];
// f[i]表示上山上到第i个景点,爬的最多的山的数量
// b[i]表示下山从第i个景点,走过的最多的山的数量
int f[N], b[N];

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

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

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

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

    printf("%d", n-ans);
    return 0;
}

1012. 友好城市 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5010;
typedef pair<int,int> PII;

int n;
PII h[N];
int f[N];
int ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf(" %d %d", &x, &y);
        h[i].first = x;
        h[i].second = y;
    }

    sort(h+1,h+n+1);

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

    printf("%d", ans);
    return 0;
}

1016. 最大上升子序列和 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;

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

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

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

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

    printf("%d", ans);

    return 0;
}

1010. 拦截导弹 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;

int w[N];
int g[N], f[N];
int n = 1;
int res = 0, cnt = 0;

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

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

    cout << res << endl;

    for (int i = 1; i < n; i++)
    {
        int k = 0;
        // 填入的同时保持其单调上升,因为后面填入的数一定比前面所有填入的数都大,才会再开一个
        while (k < cnt && g[k] < w[i])
            k++;
        g[k] = w[i];
        if (k >= cnt)
            cnt++;
    }

    cout << cnt << endl;

    return 0;
}

187. 导弹防御系统 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 55;

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

// x表示当前遍历到的导弹,uu表示上升序列数,dd表示下降序列数
void dfs(int x, int uu, int dd)
{
    // 剪枝
    if (uu + dd >= ans)
        return;

    // 搜完,并且答案比原先要小,更新答案
    if (x == n + 1)
    {
        ans = uu + dd;
        return;
    }

    // case1:将现在的导弹放到上升序列中
    int k = 0;
    while (k < uu && up[k] >= w[x])
        k++;
    int tmp = up[k];
    up[k] = w[x];
    if (k >= uu)
        dfs(x + 1, uu + 1, dd);
    else
        dfs(x + 1, uu, dd);
    up[k] = tmp; // 恢复现场

    // case2:将现在的导弹放到下降序列中
    k = 0;
    while (k < dd && down[k] <= w[x])
        k++;
    tmp = down[k];
    down[k] = w[x];
    if (k >= dd)
        dfs(x + 1, uu, dd + 1);
    else
        dfs(x + 1, uu, dd);
    down[k] = tmp;
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i++)
            cin >> w[i];

        ans = n;

        dfs(1, 0, 0);

        cout << ans << endl;
    }

    return 0;
}

272. 最长公共上升子序列 - AcWing题库

AcWing 272. 最长公共上升子序列

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf(" %d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf(" %d", &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++)
                {
                    //求1~j-1的所有公共子序列的最长值 -> 在b[j]<a[i]的时候,维护这个最长值 -> 到b[j]=a[i]的时候,直接将这个最长值赋进去
                    if (b[k] < a[i])
                        f[i][j] = max(f[i][j], f[i][k] + 1);
                }
            }
        }
    }

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

    printf("%d", ans);

    return 0;
}

AcWing 272. 最长公共上升子序列(优化版)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3010;

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

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

    for (int i = 1; i <= n; i++)
    {
        int maxn = 1;
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            // 求1~j-1的所有公共子序列的最长值 ->
            // 在b[j]<a[i]的时候,维护这个最长值 ->
            if (b[j] < a[i])
                maxn = max(maxn, f[i][j] + 1);
            // 到b[j]=a[i]的时候,直接将这个最长值赋进去
            if (b[j] == a[i])
                f[i][j] = max(f[i][j], maxn);
        }
    }

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

    printf("%d", ans);

    return 0;
}