Codeforces 682 D. Alyona and Strings (dp)

题目链接：http://codeforces.com/contest/682/problem/D

给你两个字符串，求两个字符串中顺序k个的相同子串长度之和。(注意是子串)

dp[i][j][k][0] 表示a[i] == a[j]时，a字符串前i个和b字符串前j个，顺序k个相同的子串长度之和

dp[i][j][k][1] 表示a[i] != a[j]时，顺序k个相同子串的长度之和

dp[i][j][k][0] = max(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k - 1][1], dp[i - 1][j - 1][k - 1]) + 1;

dp[i][j][k][1] = max(dp[i - 1][j][k][1], dp[i][j - 1][k][1], dp[i][j][k][0], dp[i - 1][j][k][0], dp[i][j - 1][k][0]);

渣代码...

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 1e3 + ;

 char str1[N], str2[N];

 int dp[N][N][][];

 int main()

 {

     int n, m, k;

     scanf("%d %d %d", &n, &m, &k);

     scanf("%s %s", str1, str2);

     for(int i = ; i <= n; ++i) {

         for(int j = ; j <= m; ++j) {

             for(int s = ; s <= k; ++s) {

                 if(str1[i - ] == str2[j - ]) {

                     dp[i][j][s][] = max(max(dp[i - ][j - ][s - ][], dp[i - ][j - ][s][]),

                         dp[i - ][j - ][s - ][]) + ;

                 }

                 dp[i][j][s][] = max(max(dp[i - ][j][s][], dp[i][j - ][s][]),

                     max(dp[i - ][j][s][], dp[i][j - ][s][]));

                 dp[i][j][s][] = max(dp[i][j][s][], dp[i][j][s][]);

             }

         }

     }

     printf("%d\n", dp[n][m][k][]);

     return ;

 }

巴特西

Codeforces 682 D. Alyona and Strings (dp)

最新文章

热门文章