第8章 动态规划

1007. Maximum Subsequence Sum

笔记

• $f(i)$定义为所有以$i$为右端点连续子序列的最大连续子序列和，状态转移方程为$f(i)=max(w(i), f(i-1) + w(i))$

  • 重新选区间，对应$w(i)$
  • 在原区间上继续选，对应$f(i-1) + w(i)$

• DP优化

  • $f(i)=max(w(i), f(i-1) + w(i))=max(0, f(i-1)) + w(i)$
  • 当$f(i)<0$时，可让$f(i)=0$，即重新选取区间，因为负数一定会让区间减少，故可直接舍去，此时$f(i) \geqslant 0$，$f(i)=max(0, f(i-1)) + w(i)=f(i-1)+w(i)$
  • 压缩f，使其从一维变成单个变量，即$f(i)=f(i-1)+w(i)$变为$f=f+w(i)$，进而变成f += w[i]

• 可以先实现第1问，再在第1问代码的基础上写第2问，提高效率

#include <iostream>
using namespace std;
const int N = 10010;
int n, a[N];

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

    int res = -1, l, r;
    for (int i = 1, f = -1, start; i <= n; i++) {
        if (f < 0) {
            // 重新选择区间
            f = 0;
            start = i;
        }
        f += a[i];
        if (res  < f) {
            res = f;
            l = a[start];
            r = a[i]; 
        }
    }

    if (res == -1) {
        // 全为负数
        res = 0;
        l = a[1];
        r = a[n];
    }
    cout << res << ' ' << l << ' ' << r << endl;

    return 0;
}

1045. Favorite Color Stripe

笔记

• 最长公共子序列拓展，允许字符重复多次

• DP分析

  • 状态表示$f(i,j)$

    • 集合：$p(1,j)$与$s(1,j)$的所有公共子序列的集合
    • 属性：子序列长度的最大值

  • 状态计算

    • ① 不含$p(i)$和$s(j)$：$f(i-1,j-1)$
    • ② 含$p(i)$但不含$s(j)$：用表示更大范围的$f(i,j-1)$计算（包含与①重复的区域）
    • ③ 不含$p(i)$但含$s(j)$：用表示更大范围的$f(i-1,j)$计算（包含与①重复的区域）
    • ④ 含$p(i)$和$s(j)$：当$p(i) = s(j)$时，$f(i,j-1)+1$（因为$s(i)$可以使用多次）

  • 简化

    • 由于①包含在②和③的并集中，因此只需考虑②③④即可

#include <iostream>
using namespace std;
const int M = 210, L = 1e4 + 10;
int p[M], s[L], f[M][L];
int n, m, l;


int main() {
    cin >> n;

    cin >> m;
    for (int i = 1; i <= m; i++) cin >> p[i];

    cin >> l;
    for (int i = 1; i <= l; i++) cin >> s[i];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= l; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);        // 只选其中一种
            if (p[i] == s[j])
                f[i][j] = max(f[i][j], f[i][j - 1] + 1);    // 都选
        }

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

    return 0;
}

1068. Find More Coins

笔记

• 可参考《算法提高课》“背包问题求具体方案”和“01背包问题”

• 01背包问题（恰好装满背包）

  • 状态表示$f(i,j)$
    • 集合：只考虑前$i$个物品，总体积恰好为$j$的选法
    • 属性：字典序最小

  • 状态计算

    • 不选第$i$个物品：$f(i-1,j)$
    • 选第$i$个物品：当$j \geqslant v(i)$时，$f(i-1,j-v(i))$

  • 边界：$f(0,0)=0$

• 当存在多种方式时，本题要求的是字典序最小的，而不是个数最少的，由于在求具体方案时，是倒着求解的，因此可以先降序排序，从前往后动态规划，然后再倒着求具体方案，就能得到字典序最小的方案

• 注意初值$f(0,0)=true$，物品保存至$1$ ~ $n$时，遍历物品就要遍历$1$ ~ $n$，但体积j要从$0$开始遍历到$m$

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 110;
int n, m, v[N];
bool f[N][M];

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

    sort(v + 1, v + n + 1, greater<int>());

    f[0][0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = f[i][j] | f[i - 1][j - v[i]];
        }

    if (!f[n][m]) puts("No Solution");
    else {
        string res;
        while(n) {
            if (m >= v[n] && f[n - 1][m - v[n]]) {
                res += to_string(v[n]) + ' ';
                m -= v[n];
            }
            n--;
        }
        res.pop_back();
        cout << res << endl;
    }

    return 0;
}

1093. Count PAT’s

笔记

• 状态机模型：有多少种走法

• 状态机DP

  • 状态表示$f(i,j)$
    • 集合：只考虑前$i$个字母，且走到状态$j$的所有路径
    • 属性：数量
  • 状态计算，假设$p=\text{PAT}$
    • 跳过第$i$个字母：$f(i-1,j)$
    • 选择第$i$个字母：当$p(j)=s(i)$时，$f(i-1,j-1)$

• 注意

  • 主串s和模式串p都是从下标$1$开始存储内容，且模式串p第$0$个字符必须是主串中没有的字符，本题可取空格
  • 由于本题求的是方案数，因此初始条件是$f(0,0)=1$

 #include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 4, MOD = 1000000007;
int f[N][M];
char s[N], p[] = " PAT";

int main() {
    cin >> s + 1;       // 从下标1开始存储
    int n = strlen(s + 1);


    f[0][0] = 1;
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j <= 3; j++) {
            f[i][j] = f[i - 1][j];
            if (s[i] == p[j]) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % MOD;
        }

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

    return 0;
}

1101. Quick Sort

笔记

• 用两个辅助数组可把时间复杂度从$O(n^2)$降为$O(n)$

  • l[i]表示a[1]~a[i]的最大值
  • r[i]表示a[i]~a[n]的最小值

• 边界情况

  • 由于所有数都是正整数，因此边界l[0]为$0$时，能解决i=1时判断a[i] > l[i - 1]的情况
  • 由于所有数都是正整数$\leqslant 10^9$，因此边界r[n+1]为$2\times10^9$时，能解决i=n时判断a[i] < r[i + 1]的情况

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10, INF = 2e9;
int n, a[N];
int l[N];       // 数组a下标为1~i中的最大值
int r[N];       // 数组a下标为i~n中的最小值

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

    for (int i = 1; i <= n; i++) l[i] = max(l[i - 1], a[i]);

    r[n + 1] = INF;
    for (int i = n; i; i--) r[i] = min(r[i + 1], a[i]);

    vector<int> res;
    for (int i = 1; i <= n; i++)
        if (a[i] > l[i - 1] && a[i] < r[i + 1])
            res.push_back(a[i]);

    int m = res.size();
    if (m) {
        cout << m << endl;
        cout << res[0];
        for (int i = 1; i < m; i++)
            cout << ' ' << res[i];
        cout << endl;
    } else puts("0\n");

    return 0;
}