傳送門

題目描述?Description

有兩個僅包含小寫英文字母的字符串A和B。現在要從字符串A中取出k個互不重疊的非空子串，然后把這k個子串按照其在字符串A中出現的順序依次連接起來得到一個新的字符串，請問有多少種方案可以使得這個新串與字符串B相等？注意：子串取出的位置不同也認為是不同的方案。

輸入描述?Input Description

第一行是三個正整數n，m，k，分別表示字符串A的長度，字符串B的長度，以及問題描述中所提到的k，每兩個整數之間用一個空格隔開。?

第二行包含一個長度為n的字符串，表示字符串A。 第三行包含一個長度為m的字符串，表示字符串B。

?

輸出描述?Output Description

輸出共一行，包含一個整數，表示所求方案數。由于答案可能很大，所以這里要求輸出答案對1,000,000,007取模的結果。

樣例輸入?Sample Input

【Input1】

6 3 1?

aabaab?

aab

【Input2】

6 3 2?

aabaab?

aab

【Input3】

6 3 3?

aabaab?

aab

?

樣例輸出?Sample Output

【Output1】

2

【Output2】

7

【Output3】

7

數據范圍及提示?Data Size & Hint

對于第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+滾動數組降維。

? ?? ? ? ?f[j][p][1]表示匹配s2的前j個數，劃分為p個互不重疊的非空子串，取當前s1位置的數的方案。

? ? ? ? ??f[j][p][0]表示匹配s2的前j個數，劃分為p個互不重疊的非空子串，不取當前s1位置的數的方案加上取當前s1位置的數的方案（即全部方案）。

? ? ? ? ? 當s1[i]==s2[j]時。

? ? ? ? ?f[j][p][1]=f[j-1][p-1][0]+f[j-1][p][1],由于取了s1當前位置的前一個數劃分為p個互不重疊的非空子串的方案，那么s1當前位置必須與前一個字符在同一個子串中，因此s1當前位置字符的前一個字符必須取。

? ? ? ? ?f[j][p][0]=f[j][p][0]+f[j][p][1];

? ? ? ? ?當s1[i]!=s2[j]時，

? ? ? ? f[j][p][1]=0，（0<p<min(j,k)）

#include<cstdio> #include<iostream> #define M 1000000007 #define N 210 using namespace std; int n,m,k,sum=0; char s1[1010],s2[N]; int f[N][N][2]={0}; int main() {scanf("%d%d%d",&n,&m,&k);cin>>s1+1;cin>>s2+1;f[0][0][0]=1;for (int i=1;i<=n;i++){for (int j=m;j>=1;j--)if (s1[i]==s2[j])for (int p=1;p<=min(k,j);p++){f[j][p][1]=(f[j-1][p-1][0]+f[j-1][p][1])%M; f[j][p][0]=(f[j][p][0]+f[j][p][1])%M;}else for (int p=1;p<=min(k,j);p++)f[j][p][1]=0;}printf("%d\n",f[m][k][0]);return 0; }

?

轉載于:https://www.cnblogs.com/sjymj/p/5837294.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的codevs 4560 NOIP2015 D2T2 子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。