傳送門

Solution

DP+滾動(dòng)數(shù)組.
DP狀態(tài)
$dp[i][j][k]$: $A$的第$i$個(gè)字符和$B$的第$j$個(gè)字符匹配且該字符在第$k$個(gè)子串中的方案數(shù).
轉(zhuǎn)移方程
$dp[0][0][0]=1$
$dp[i][j][k] = dp[i-1][j-1][k] + \sum\limits _{0\le i' <i} dp[i'][j-1][k-1]$

用數(shù)組$sum[j][k]$維護(hù)轉(zhuǎn)移時(shí)用到的那個(gè)和$\sum\limits _{0\le i' <i} dp[i'][j-1][k-1]$.

三維數(shù)組會(huì)MLE, 要用滾動(dòng)數(shù)組優(yōu)化成二維, 把第一維去掉.

Implementation

注意計(jì)算的順序

#include <bits/stdc++.h> using namespace std;const int N=1005, M=205, K=205, mod=1e9+7;int dp[M][K];char a[N], b[N];int sum[M][K];int main(){int n, m, K;scanf("%d%d%d", &n, &m, &K);scanf("%s%s", a+1, b+1);dp[0][0]=1;sum[0][0]=1;for(int i=1; i<=n; i++){for(int j=m; j>0; j--){if(a[i]!=b[j]){for(int k=1; k<=K; k++)dp[j][k]=0;}else{for(int k=1; k<=K; k++){dp[j][k]=(dp[j-1][k]+sum[j-1][k-1])%mod;sum[j][k]+=dp[j][k];sum[j][k]%=mod;}}}}printf("%d\n", sum[m][K]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Patt/p/6057644.html

總結(jié)

以上是生活随笔為你收集整理的UOJ #149 [NOIP 2015] 子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。