一、背包

乱八七糟

不知道叫啥但是很常见的一个dp

1.PTA1093 Count PAT’s

大致意思就是说给一串字符串，然后问其中abcd顺序的字符串有多少个，模板代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 1000000007;
LL f[N][5];

int main() {
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    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') {
            f[i][0] = (f[i][0] + 1) % mod;
        } else if (s[i] == 'A') {
            f[i][1] = (f[i][1] + f[i - 1][0]) % mod;
        } else if (s[i] == 'T') {
            f[i][2] = (f[i][2] + f[i - 1][1]) % mod;
        }
    }
    cout << f[n][2] << endl;

    return 0;
}

2.AcWing 1884. COW

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL f[N][5];

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j < 3; j ++ ) {
            f[i][j] = f[i - 1][j];
        }
        if (s[i] == 'C') {
            f[i][0] = f[i][0] + 1;
        } else if (s[i] == 'O') {
            f[i][1] = f[i][1] + f[i - 1][0];
        } else if (s[i] == 'W') {
            f[i][2] = f[i][2] + f[i - 1][1];
        }
    }
    cout << f[n][2] << endl;

    return 0;
}