前言
思路
很明显的动态规划题目,但是我就是想不到,我想到以子序列为dp的目标,但是没有想到以字符串k为dp目标。
多尝试不同的条件,说不定就能碰出火花,不能懒!
记住,动态规划不是一步就达到答案的,是一步一步转化之后才到达答案的。 表示前i个定序列匹配到字符串k第j位的所有合法方案, 所以分为取和不取两种选择,这就类似于01背包了,但是比01背包多了一个点就是取之前需要判断它是否能拼接成字符串k。
所以状态转移方程为 :
利用滚动数组,将状态转移方程进一步转化为 :
使用之前的值,所以别忘记了是逆序遍历。
AC代码
#include<bits/stdc++.h> using namespace std; #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define For(i, a, b) for (int i = (a); i >= (b); --i) #define mod(x) (x) % 1000000007 #define debug(a) cout << #a << " = " << a << endl; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi; const int N = 5000000 + 10, P = 131, M = 50; ull p[N], h[N], ha[M]; ll f[N]; int n, len[M]; char k[N], a[M][N]; bool check(ull hash, int l, int r) { return hash == h[r] - h[l - 1] * p[r - l + 1]; } int main() { #ifdef LOCAL freopen("data.in", "r", stdin); #endif ios::sync_with_stdio(false); cout.tie(0); cin.tie(0); cin >> n >> k + 1; int sz = strlen(k + 1); p[0] = 1; _rep(i, 1, 5e6) { p[i] = p[i - 1] * P; if (i <= sz) h[i] = h[i - 1] * P + k[i]; } _rep(i, 1, n) { cin >> a[i] + 1; len[i] = strlen(a[i] + 1); _rep(j, 1, len[i]) ha[i] = ha[i] * P + a[i][j]; } f[0] = 1; _rep(i, 1, n) For(j, sz, len[i]) f[j] += f[j - len[i]] * check(ha[i], j - len[i] + 1, j); cout << f[sz] << endl; return 0; }