第一题

原题链接

题目描述

有两个仅包含小写英文字母的字符串A和B。

现在要从字符串A中取出k个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串 B 相等？

注意：子串取出的位置不同也认为是不同的方案。

输入格式

第一行是三个正整数 n，m，k，分别表示字符串 A 的长度，字符串 B 的长度，以及问题描述中所提到的 k，每两个整数之间用一个空格隔开。

第二行包含一个长度为 n 的字符串，表示字符串A。 

第三行包含一个长度为 m 的字符串，表示字符串B。

输出格式

输出共一行，包含一个整数，表示所求方案数。

由于答案可能很大，所以这里要求输出答案对 1,000,000,007 取模的结果。

数据范围

$$ 1 \le n \le 1000, \\\\ 1 \le m \le 200,\\\\ 1 \le k \le m\\\\ $$

输入样例：

6 3 1
aabaab
aab

输出样例：

2

解题报告

题意理解

就是让你从字符串A中,拿出$k$个子串,子串之间不得有重复,要求$k$个子串,按照拿出来的顺序,可以拼接成为字符串B.

要你求出符合条件的方案总数.

所有合法方案如下：（加下划线的部分表示取出的子串）

样例一：aab aab / aab aab

样例二：a ab aab / a aba ab / a a ba ab / aab a ab / aa b aab / aa baa b / aab aa b

样例三：a a b aab / a a baa b / a ab a a b / a aba a b / a a b a a b / a a ba a b / aab a a b

思路解析

算法确定

一般来说,当我们看到由于答案可能很大，所以这里要求输出答案对 1,000,000,007 取模的结果。这句话的时候,一般来说动态规划算法是可以基本确定的了.

每一个字符串,其实我们都可以看作是字符区间.

我们接着来分析题目的内容.

我们发现,对于题目而言,一个非常重要的点就是,他是一个区间.

区间有关的动态规划,最基本的有哪些呢?

1. 区间DP
2. 线性DP
3. 数位DP

我们发现线性DP似乎是一个不错的选择,因为区间DP,这道题目似乎并木有给出明显的区间划分,反而都是线性的思想比较明显.

至于数位DP跟本题没有任何关系.

所以现在我们完全可以确定,本题的算法就是线性动态规划

状态设置

我们观察这个题目,题目的大致意思,就是让我们选取一些字符串出来,去构造字符串B.

那么我们状态中,必须有以下这些信息.

1. 关于字符串A的信息.
2. 关于字符串B的信息
3. 我们当前用了多少个字符串,因为我们最多只能选取k个字符串.

这就是我们可以确定的必备信息条件,那么接下来我们如何设置状态表示呢?

根据上面的信息表,我们不难想到我们的基本状态如何设置.
$$ f[i][j][k]表示为字符串A的前i个字符,我们已经选出了j个字符匹配字符串B,然后我们一共取出了K个字符串. $$
举个例子,让我们更好的理解一下.
$$ 比如说f[5][4][2]表示为 \\\ 我们选取了5个字符在串A中,然后其中有四个字符匹配字符串B,我们一共取出了2个字符串. \\\\ 串A:ABCBD \\\\ 串B:ABBD \\\\ 那么显然我们从字符串A中选取出来的是AB,BD,中间的C被我们抛弃了. \\\\ $$
但是我们发现我们的状态转移方程不太好想出来,为什么呢?

我们发现对于K的转移,我们很难划分.

比如说我们当前选择了第$j$个字符.

但是我们不知道我们之前的$j-1$这个字符是否选择了.

如果选择了,那么我们的k不需要变化.

没有选择,我们的k就需要+1.

综上所述,我们不得不处理以下这个选取问题.

我们可以增加一个维度,去存储当前字符是否选择了.
$$ f[i][j][k][0/1]表示为串A前i个字符,选取了j个字符,一共选取了k个字符串 \\\\ 0表示第i个字符没有选择,1表示第i个字符选择了1 \\\\ $$

转移方程

1.当前$a[i]==b[j]$

这是什么意思?就是我们当前这个字符,可以匹配B串了.

f[i][j][k][1]=(f[i-1][j-1][k][1]+f[i-1][j-1][k-1][0])%Mod;
f[i][j][k][0]=(f[i-1][j-1][k][0]+f[i][j][k][1])%Mod;

我们来慢慢分析每一句话.

f[i][j][k][1]=(f[i-1][j-1][k][1]+f[i-1][j-1][k-1][0])%Mod;

对于这句话而言.

假如说,我们当前选择第$i$个字符.
$$ f[i-1][j-1][k][1]表示为 \\\\ 前i-1个字符串中,选择了j-1个字符,同时i-1个字符我们也选择了 \\\\ 因为我们这个字符和前面的字符相连接了,所以我们不需要更多的代价 \\\\ f[i-1][j-1][k-1][0]表示为 \\\\ 前i-1个字符串中,选择了j-1个字符,但是i-1个字符我们没有选择 \\\\ 所以只能使用k-1个字符串,因为我们当前字符得花费一个字符串代价. \\\\ $$
接着我们分析第二句话.

f[i][j][k][0]=(f[i-1][j-1][k][0]+f[i][j][k][1])%Mod;

假如说我们当前不选择第$i$个字符.

就是这一位取的+这一位没取的（也就是上一段的0）

Hint:空间太大,所以我们要状态压缩.

我们发现第一维$i$其实并没有什么作用.

所以我们使用背包问题的优化思想,让循环反过来,然后这道题目就解决了.

#include <bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
#define read() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) //读入优化
string a,b;
int n,m,k2,f[210][210][2];
int main()
{
    read();
    cin>>n>>m>>k2>>a>>b;
    a=" "+a;//字符串有用部分从1开始
    b=" "+b;//字符串有用部分从1开始
    f[0][0][0]=1;
    for(int i=1; i<=n; i++)
        for(int j=m; j; j--)//循环反过来
            if (a[i]==b[j])//相等判定
            {
                for(int k=min(j,k2); k; k--)//k必然小于j,而且不能超过范围
                {
                    f[j][k][1]=(f[j-1][k][1]+f[j-1][k-1][0])%Mod;
                    f[j][k][0]=(f[j][k][0]+f[j][k][1])%Mod;
                }
            }
            else
                for(int k=1; k<=m; k++)//初始化把
                    f[j][k][1]=0;
    cout<<(f[m][k2][0])%Mod;
    return 0;
}