板子

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf ("%d %d", &n, &m);
    scanf ("%s %s", a + 1, b + 1); // 下标要从1开始

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]); // Max(不考虑a[i] 考虑b[j], 考虑a[i] 不考虑b[j])
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); // 如果两个字符相等,那么两个可以同时考虑
        }

    printf ("%d", f[n][m]);
    return 0;
}

例题

5.洛谷:P1819公共子序列

先预处理出来$ne$数组,以便快速找到三个字符串中$i$位置往后字母$j$第一次出现的位置(如果没有则为$INF$)
然后再跑一遍记忆化搜索即可

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 160, INF = 0x3f3f3f3f, mod = 1e8;

int n;
char s[4][N];
int ne[4][N][30];
int f[N][N][N];

void init(int x)
{
    memset(ne[x], 0x3f, sizeof ne[x]);

    for (int i = n - 1; i >= 0; i --)
        for (int j = 0; j < 26; j ++)
        {
            ne[x][i][j] = ne[x][i + 1][j]; // 先覆盖ne[i][j]的值，然后再更新i + 1那个字符的ne值
            ne[x][i][s[x][i + 1] - 'a'] = i + 1; // 这里太妙了！(需要细细评味)
        }
}

int dfs(int x, int y, int z)
{
    if (f[x][y][z]) return f[x][y][z]; // 如果不记忆化搜索的话会TLE

    int res = 1; // 这里如果x = y = z = 0时应该res = 0,但是要保证后续res为1,则在最后答案减去1即可
    for (int i = 0; i < 26; i ++)
    {
        int a = ne[0][x][i], b = ne[1][y][i], c = ne[2][z][i]; // 找到三个字符串中第一个字母('a' + i)

        if (a == INF || b == INF || c == INF) continue; // 如果有一个字符串没有就代表不是公共的

        res = (res +  dfs(a, b, c) % mod) % mod;
    }

    return f[x][y][z] = res; // 记忆化搜索
}

int main()
{
    scanf ("%d", &n);

    for (int i = 0; i < 3; i ++) scanf ("%s", s[i] + 1);

    init(0), init(1), init(2);

    printf ("%d", (dfs(0, 0, 0) - 1) % mod);
    return 0;
}

6.Multiplicity
这题暴力我都打半天
题解里的暴力都说是$$O(N^2)$$
为什么我的是O(N^3)

$$ 优化的关键就是先把二维优化成一位(空间复杂度解决) $$
$$ 找所有数字的因子然后枚举因子就可以=>把枚举时O(N)的复杂度降到了O(\sqrt{N}) $$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100100, mod = 1e9 + 7;

int n;
int a[N], cnt[N], son[N];
int f[N]; // 发现这题第一维可以优化掉

int main()
{
    scanf ("%d", &n);

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

    f[0] = 1;

    for (int i = 1; i <= n; i ++)
    {
        for (int k = 1; k <= a[i] / k; k ++) // 找到a[i]的所有因子
            if (a[i] % k == 0)
            {
                if (k <= n) son[cnt[i] ++] = k; // 如果大于n的就不需要了,因为b序列长度最多为n
                if (k != a[i] / k && a[i] / k <= n) son[cnt[i] ++] = a[i] / k;
            }

        sort(son, son + cnt[i]); // 再排序一下

        for (int j = cnt[i] - 1; j >= 0; j --) // 一定是逆序循环，保证不会算重复
            f[son[j]] = (f[son[j]] + f[son[j] - 1]) % mod;
    }

    int res = 0;

    for (int i = 1; i <= n; i ++) res = (res + f[i]) % mod;

    printf ("%d", res);

    return 0;
}