首页 > 代码库 > [luoguP2679] 子串（DP）
[luoguP2679] 子串（DP）
传送门
气死我了，自己YY的方法只能得70分。
一个下午都在搞这道题。
至于正解，真的不想写了。
请移步 here
#include <cstdio>#define M 201#define N 1001#define p 1000000007#define LL long longint n, m, t;char A[N], B[M];LL f[2][M][M], sum[2][M][M];int main(){ int i, j, k; scanf("%d %d %d", &n, &m, &t); scanf("%s %s", A + 1, B + 1); for(i = 1; i <= n; i++) { sum[(i & 1) ^ 1][0][0] = 1; for(j = 1; j <= m; j++) for(k = 1; k <= t; k++) { if(A[i] != B[j]) f[i & 1][j][k] = 0; if(A[i] == B[j]) f[i & 1][j][k] = (f[(i & 1) ^ 1][j - 1][k] + sum[(i & 1) ^ 1][j - 1][k - 1]) % p; sum[i & 1][j][k] = (sum[(i & 1) ^ 1][j][k] + f[i & 1][j][k]) % p; } } printf("%lld\n", sum[n & 1][m][t]); return 0;}
[luoguP2679] 子串（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。