[NOIP2015 提高组] 子串
题目背景
NOIP2015 Day2T2
题目描述
有两个仅包含小写英文字母的字符串 $A$ 和 $B$。
现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串,然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等?
注意:子串取出的位置不同也认为是不同的方案。
输入格式
第一行是三个正整数 $n,m,k$,分别表示字符串 $A$ 的长度,字符串 $B$ 的长度,以及问题描述中所提到的 $k$,每两个整数之间用一个空格隔开。
第二行包含一个长度为 $n$ 的字符串,表示字符串 $A$。
第三行包含一个长度为 $m$ 的字符串,表示字符串 $B$。
输出格式
一个整数,表示所求方案数。
由于答案可能很大,所以这里要求输出答案对 $1000000007$ 取模的结果。
样例 #1
样例输入 #1
6 3 1
aabaab
aab
样例输出 #1
2
样例 #2
样例输入 #2
6 3 2
aabaab
aab
样例输出 #2
7
样例 #3
样例输入 #3
6 3 3
aabaab
aab
样例输出 #3
7
数据范围
对于第 1 组数据:$1≤n≤500,1≤m≤50,k=1$;
对于第 2 组至第 3 组数据:$1≤n≤500,1≤m≤50,k=2$;
对于第 4 组至第 5 组数据:$1≤n≤500,1≤m≤50,k=m$;
对于第 1 组至第 7 组数据:$1≤n≤500,1≤m≤50,1≤k≤m$;
对于第 1 组至第 9 组数据:$1≤n≤1000,1≤m≤100,1≤k≤m$;
对于所有 10 组数据:$1≤n≤1000,1≤m≤200,1≤k≤m$。
解题思路
当我们需要选择i位置的字符的时候,我们其实分为三种情况,分别是我们上一个不选(k需要变化),上一个选,但是上一个选(k变化)也需要考虑进去。因为我们可能两个选择的子串相邻。
代码
import java.util.*;
import java.io.*;
class Main{
public static int N = 1010,M = 210,P = 1000000007 ;
public static long[][][][] dp = new long[N][M][M][2];
public static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int n = sc.nextInt(),m = sc.nextInt(),K = sc.nextInt();
String s = sc.next(),t = sc.next();
for(int i = 0;i <= n;i++) dp[i][0][0][0] = 1;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
for(int k = 1;k <= K;k++)
{
if(s.charAt(i-1) == t.charAt(j-1))
dp[i][j][k][1] = (dp[i-1][j-1][k][1] + dp[i-1][j-1][k-1][0] + dp[i-1][j-1][k-1][1])%P;
dp[i][j][k][0] = (dp[i-1][j][k][1] + dp[i-1][j][k][0])%P;
}
System.out.println((dp[n][m][K][1] + dp[n][m][K][0])%P);
}
}
上面的代码无疑会mle。我们需要使用滚动数组优化一维
import java.util.*;
import java.io.*;
class Main {
public static int N = 1010, M = 210, P = 1000000007;
public static int[][][][] dp = new int[2][M][M][2]; // 使用滚动数组优化
public static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int n = sc.nextInt(), m = sc.nextInt(), K = sc.nextInt();
String s = sc.next(), t = sc.next();
for (int i = 0; i <= n; i++) dp[i % 2][0][0][0] = 1; // 初始化优化
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 1; k <= K; k++) {
dp[i % 2][j][k][0] = 0; // 重置当前状态
dp[i % 2][j][k][1] = 0; // 重置当前状态
if (s.charAt(i - 1) == t.charAt(j - 1))
dp[i % 2][j][k][1] = (int)(((long)dp[(i - 1) % 2][j - 1][k][1] + dp[(i - 1) % 2][j - 1][k - 1][0] + dp[(i - 1) % 2][j - 1][k - 1][1]) % P);
dp[i % 2][j][k][0] = (int)(((long)dp[(i - 1) % 2][j][k][1] + dp[(i - 1) % 2][j][k][0]) % P);
}
System.out.println((int)(((long)dp[n % 2][m][K][1] + dp[n % 2][m][K][0]) % P));
}
}