洛谷题单指南-动态规划2-P2679 [NOIP2015 提高组] 子串

原题链接：https://www.luogu.com.cn/problem/P2679

题意解读：在a中按顺序挑选k个子串，使得这些子串连在一起正好和b相等，求方案数。

解题思路：

这样的题目，无外乎两个思路：DFS暴搜（得部分分）、动态规划

动态规划不好想，还是先暴搜吧！

1、DFS暴搜

搜索的思路就是：从a起始位置开始，一直找到跟b前缀相等的字符，然后枚举连续有多少个字符相等，都作为一种可能方案，

再把相等的前缀拿掉，相应子串数量+1，对a、b剩下的部分继续进行dfs，

当然，为了尽可能时间最优，还需要进行合理的剪枝：

剪枝操作1：如果已经累计找到超过k个子串了还没有匹配上，就不用再继续了

剪枝操作2：如果a剩下的长度比b剩下的长度小，也不用再继续判断了

40分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = 205, MOD = 1000000007;
string a, b;
int n, m, k, ans;

//从a的ai开始，枚举子串和b的bi开始的前缀匹配，匹配上数量cnt+1
void dfs(int ai, int bi, int cnt)
{
    if(cnt == k && bi == b.size())
    {
        ans = (ans + 1) % MOD;
        return;
    }
    if(cnt >= k) return; //剪枝：超过k个子串，不需要再继续处理
    if(a.size() - ai < b.size() - bi) return; //剪枝：a剩下的长度比b剩下的小，a的子串永远不能等于b
    for(int i = ai; i < a.size(); i++)
    {
        if(a[i] == b[bi]) //如果找到a、b相等的位置
        {
            int j = 0;
            while(i + j < a.size() && bi + j < b.size() && a[i + j] == b[bi + j]) //往后枚举所有相等的前缀，作为一种方案，并继续dfs
            {
                dfs(i + j + 1, bi + j + 1, cnt + 1);
                j++;
            }
        }
    }
}

int main()
{
    cin >> n >> m >> k >> a >> b;
    dfs(0, 0, 0);
    cout << ans;
    return 0;
}

2、动态规划

首先，思考状态表示，

本题直观上需要三个状态：以a[i]为终点，与b[1~j]匹配，且子串数为p的总方案数，

但是，由于不是每一个a[i]为终点都能和b[1~j]匹配，要匹配必须有a[i] = b[j]，

所以对于每一个i，a[i]这个终点可以用也可以不用，干脆定义两个状态：

f[i][j][p]：表示以a[i]为终点（a[i]使用），和b[1~j]匹配，且子串数是p的方案数

g[i][j][p]：表示以a[i]为终点（a[i]不使用），和b[1~j]匹配，且子串数是p的方案数

状态转移为：

当a[i] == b[j]时，可以使用a[i]作为终点，也可以不使用a[i]作为终点，f，g都要转移

  f[i][j][p] = f[i-1][j-1][p-1] + g[i-1][j-1][p-1] + f[i-1][j-1][p]，

    使用a[i]作为终点的方案 = a[i]单独作为子串的方案 + a[i]跟前面一起作为子串的方案

    a[i]单独作为子串的方案 = a[i-1]作为终点的方案 + a[i-1]不作为终点的方案 = f[i-1][j-1][p-1] + g[i-1][j-1][p-1]

    a[i]跟前面一起作为子串的方案 = a[i-1]作为终点的方案 =  f[i-1][j-1][p]，注意这里还是p，而不是p-1，因为a[i]没有单独成一个子串    

  g[i][j][p]  = f[i-1][j][p] + g[i-1][j][p]，

    不使用a[i]作为终点的方案 = 使用a[i-1]作为终点的方案 + 不使用a[i-1]作为终点的方案

当a[i] != b[j]时，只能不使用a[i]作为终点，g需要转移，f对应的方案是0

  f[i][j][p] = 0，

    因为a[i] != b[j]，所以使用a[i]作为终点来匹配b[1~j]的方案数是0

  g[i][j][p] = f[i-1][j][p] + g[i-1][j][p]，

    不使用a[i]作为终点的方案 = 使用a[i-1]作为终点的方案 + 不使用a[i-1]作为终点的方案

初始化：f[i][0][0] = 1, i从0~n，以i为终点、和空串匹配、选0个子串的方案是1

答案就是f[n][m][k] + g[n][m][k]

注意：空间复杂度是n * m * k * 4 * 2 = 1000 * 200 * 200 * 4 * 2 = 320M，肯定是不行的

但从递推式来看i只依赖i-1，可以用优化掉一维，先写出三维的代码，只针对1~7数据点，n=500，m=50

70分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 505, M = 55, MOD = 1000000007;
string a, b;
int n, m, k;
int f[N][M][M], g[N][M][M];

int main()
{
    cin >> n >> m >> k >> a >> b;
    a = " " + a; //使字符串从1开始
    b = " " + b; //使字符串从1开始
    f[0][0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        f[i][0][0] = 1;
        for(int j = 1; j <= m; j++)
        {
            for(int p = 1; p <= k; p++)
            {
                if(a[i] == b[j])
                {
                    f[i][j][p] = ((f[i-1][j-1][p-1] + g[i-1][j-1][p-1]) % MOD + f[i-1][j-1][p]) % MOD;
                    g[i][j][p] = (f[i-1][j][p] + g[i-1][j][p]) % MOD;
                }
                else
                {
                    f[i][j][p] = 0;
                    g[i][j][p] = (f[i-1][j][p] + g[i-1][j][p]) % MOD;
                }
            }
        }
    }
    cout << (f[n][m][k] + g[n][m][k]) % MOD;
    return 0;
}

再基于70代码进行空间优化

首先，将N、M定义为1005, 205

其次，由于递推关系中i只依赖i-1，可以将f[N][M][M]，g[N][M][M]的第一维用滚动数组优化：f[2][M][M]，g[2][M][M]

最后，定义now，old变量，每次i枚举时交换位置，达到0/1交替滚动的效果

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = 205, MOD = 1000000007;
string a, b;
int n, m, k;
int f[2][M][M], g[2][M][M];

int main()
{
    cin >> n >> m >> k >> a >> b;
    a = " " + a; //使字符串从1开始
    b = " " + b; //使字符串从1开始
    f[0][0][0] = f[1][0][0] = 1;
    int now = 0, old = 1; //滚动数组
    for(int i = 1; i <= n; i++)
    {
        swap(now, old); //交替滚动
        for(int j = 1; j <= m; j++)
        {
            for(int p = 1; p <= k; p++)
            {
                if(a[i] == b[j])
                {
                    f[now][j][p] = ((f[old][j-1][p-1] + g[old][j-1][p-1]) % MOD + f[old][j-1][p]) % MOD;
                    g[now][j][p] = (f[old][j][p] + g[old][j][p]) % MOD;
                }
                else
                {
                    f[now][j][p] = 0;
                    g[now][j][p] = (f[old][j][p] + g[old][j][p]) % MOD;
                }
            }
        }
    }
    cout << (f[now][m][k] + g[now][m][k]) % MOD;
    return 0;
}