NOIP 2015 D2T2: 子串 —— 动态规划

传送门

题目描述:

有两个仅包含小写英文字母的字符串 $A$ 和 $B$。现在要从字符串 $A$ 中取出 k 个互不重叠的非空子串,然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 $B$ 相等?注意:子串取出的位置不同也认为是不同的方案。

输入格式:

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

输出格式:

输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,007 取模的结果

测试样例:

Input
6 3 1
aabaab
aab
Output
2
Input
6 3 2
aabaab
aab
Output
7
Input
6 3 3
aabaab
aab
Output
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$ 。

分析:

这题 DP 。

我们定义:

  • $dp_{i, j, k, 0}$ 代表 $A$ 字符串匹配到第 $i$ 位, $B$ 字符串匹配到第 $j$ 位,取出了 $k$ 个子串的方案数。
  • $dp_{i, j, k, 1}$ 代表 $A$ 字符串匹配到第 $i$ 位并且要选 $A$ 的第 $i$ 的字符, $B$ 字符串匹配到第 $j$ 位的方案数。

转移分两种情况:

  • $A_i = B_j$ :当两个字符相等时,选 $A_i$ 的方案数( $dp_{i, j, k, 0}$ 由两部分组成:选 $A$ 的第 $i - 1$ 位并与当前位连起来,这种情况下不消耗 $k$ ;将 $A$ 的第 $i$ 位作为新取出的一个子串, $k$ 消耗了 $1$ 。
    总方案数也有两部分:一部分是不选 $A_i$ 的方案数,这部分直接由上一位转移过来;另一部分是选 $A_i$ 的方案数,这一部分刚刚被算出来(上一段)。所以:
  • $A_i \not = B_j$ :很显然, $A_i$ 根本没有贡献,总方案数直接由上一位转移过来。而选 $A_i$ 的方案数显然是 $0$ 。所以:

这样我们就写出了最重要的转移方程。然后我们会发现另一个问题。在 $1 \leq n \leq 1000$ , $1 \leq m \leq 200$ 的数据范围下,四维的数组是开不下的。怎么办呢?我们发现,在枚举 $A_i$ 的时候, $A_i$ 的结果只会被它的前一位影响,所以我们用滚动数组滚一滚就好了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = (_x << 3) + (_x << 1) + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;

const int MAX_N = 1000 + 5, MAX_M = 200 + 5, MOD = 1e9 + 7;
char a[MAX_N], b[MAX_N];
int f[2][MAX_M][MAX_M][2];
int n, m, K;
void DP() {
  f[0][0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    int cur = i & 1, pre = cur ^ 1;
    memset(f[cur], 0, sizeof(f[cur]));
    f[cur][0][0][0] = 1;
    for (int j = 1; j <= m; ++j) {
      for (int k = 1; k <= K; ++k) {
        if (a[i] == b[j]) {
          f[cur][j][k][1] = (f[pre][j - 1][k - 1][0] + f[pre][j - 1][k][1]) % MOD;
          f[cur][j][k][0] = (f[pre][j][k][0] + f[cur][j][k][1]) % MOD;
        }
        else f[cur][j][k][0] = f[pre][j][k][0];
      }
    }
  }
}

int main() {
  read(n), read(m), read(K);
  scanf("%s%s", a + 1, b + 1);
  DP();
  int ans = f[n & 1][m][K][0];
  printf("%d", ans);
  return 0;
}