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]);

渣代码...

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <ctime>
10 #include <list>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long LL;
15 typedef pair <int, int> P;
16 const int N = 1e3 + 5;
17 char str1[N], str2[N];
18 int dp[N][N][11][2];
19 
20 int main()
21 {
22     int n, m, k;
23     scanf("%d %d %d", &n, &m, &k);
24     scanf("%s %s", str1, str2);
25     for(int i = 1; i <= n; ++i) {
26         for(int j = 1; j <= m; ++j) {
27             for(int s = 1; s <= k; ++s) {
28                 if(str1[i - 1] == str2[j - 1]) {
29                     dp[i][j][s][0] = max(max(dp[i - 1][j - 1][s - 1][1], dp[i - 1][j - 1][s][0]), 
30                         dp[i - 1][j - 1][s - 1][0]) + 1;
31                 }
32                 dp[i][j][s][1] = max(max(dp[i - 1][j][s][1], dp[i][j - 1][s][1]), 
33                     max(dp[i - 1][j][s][0], dp[i][j - 1][s][0]));
34                 dp[i][j][s][1] = max(dp[i][j][s][0], dp[i][j][s][1]);
35             }
36         }
37     }
38     printf("%d
", dp[n][m][k][1]);
39     return 0;
40 }