AcWing 187. 导弹防御系统
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

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

void dfs(int u, int su, int sd) //当前枚举到的第几个数，当前上升子序列的个数，当前下降子序列的个数
{
    if (su + sd >= ans) return;
    if (u == n)
    {
        ans = su +  sd;
        return;
    }

    //情况1 将当前数放到上升子序列中
    int k = 0;
    while (k < su && up[k] >= q[u]) k++;
    int t = up[k];   //现场备份一下
    up[k] = q[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);  //开辟一个新的上升子序列
    up[k] = t;  // 恢复现场

    //情况2 将当前数放到下降子序列中
    k = 0;
    while (k < sd && down[k] <= q[u]) k++;
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main()
{
    while (cin >> n, n)  //输入处理方式
    {
        for (int i = 0; i < n; i++) cin >> q[i];

        ans = n;
        dfs(0, 0, 0);

        cout << ans << endl;
    }

    return 0;
}
AcWing 902. 最短编辑距离
AcWing 899. 编辑距离
AcWing 1017. 怪盗基德的滑翔翼
AcWing 1014. 登山
AcWing 482. 合唱队形

背包模型
AcWing 2. 01背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];  // 右边集合为空，不包含i
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;

    return 0;
}
二维优化到一维
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
//int f[N][N];
int f[N];   
//计算f[i]这一层，只用到了f[i-1]这一层的数据，用滚动数组
//然后f[i][j - v[i]]都是用到小于j的，不会用到j右侧的

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

    for (int i = 1; i <= n; i++)
        //for (int j = v[i]; j <= m; j++)
        for (int j = m; j >= v[i]; j--)
        {
            //f[i][j] = f[i - 1][j];  // 右边集合为空，不包含i
            //f[j] = f[j];
            //if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            //f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //第i层算的是f[i][j]
            //f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            // f[i - 1][j - v[i]]是严格小于j的，从小到大枚举的
            //计算f[j - v[i]], 但他在j层之前第i层已经被计算过了，
            //那么f[j - v[i]]其实是第i层的j - v[i], 等价于f[i][j - v[i]]

            //这与我们的刚才的二维里的状态计算不一致，刚才实际应该是f[i - 1][j - v[i]]
            //若j从大到小枚举，算f[j]的时候，f[j - v[i]]还没有被更新过，存的就是f[i - 1][j - v[i]]
            //这样就和二维的状态转移方程等价了

        }

    //cout << f[n][m] << endl;
    cout << f[m] << endl;

    return 0;
}