#include <iostream> #include <string> using namespace std; int n, k, t, mts[8003], dp[8003][8003][3]; string s; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); cin >> n >> k >> t >> s; for (int i = 1; i <= n; i++) { mts[i] = mts[i - 1] + (s[i - 1] == '1' || s[i - 1] == '2' ? 1 : 0); } for (int i = 0; i <= n + 2; i++) for (int j = 0; j <= k + 2; j++) for (int st = 0; st < 3; st++) dp[i][j][st] = -1000000000; dp[1][0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { for (int st : {0, 1, 2}) { int cur = dp[i][j][st]; if (cur == -1000000000) continue; char c = s[i - 1]; if (st == 0 || st == 2) { if (c == '1') { if (j < k) dp[i + 1][j + 1][st] = max(dp[i + 1][j + 1][st], cur + 1); } else if (c == '2') { dp[i + 1][j][st] = max(dp[i + 1][j][st], cur); if (j < k) dp[i + 1][j + 1][st] = max(dp[i + 1][j + 1][st], cur + 1); } else { dp[i + 1][j][st] = max(dp[i + 1][j][st], cur + 1); } if (st == 0 && i + 2 * t <= n) { int miss = mts[i + t - 1] - mts[i - 1]; if (j + miss <= k) { dp[i + t][j + miss][1] = max(dp[i + t][j + miss][1], cur); } } } else if (st == 1) { if (c == '1' || c == '2') { dp[i + 1][j][1] = max(dp[i + 1][j][1], cur); if (j < k) dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1], cur); } else { dp[i + 1][j][1] = max(dp[i + 1][j][1], cur); } if (i + t <= n + 1) { int miss = mts[i + t - 1] - mts[i - 1]; if (j + miss <= k) { dp[i + t][j + miss][2] = max(dp[i + t][j + miss][2], cur); } } } } } } int ans = -1; for (int j = 0; j <= k; j++) { ans = max(ans, dp[n + 1][j][0]); ans = max(ans, dp[n + 1][j][2]); } cout << (ans < 0 ? -1 : ans) << endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <iostream> #include <string> using namespace std; int n, k, t, mts[8003], dp[8003][8003][3]; string s; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); cin >> n >> k >> t >> s; for (int i = 1; i <= n; i++) { mts[i] = mts[i - 1] + (s[i - 1] == '1' || s[i - 1] == '2' ? 1 : 0); } for (int i = 0; i <= n + 2; i++) for (int j = 0; j <= k + 2; j++) for (int st = 0; st < 3; st++) dp[i][j][st] = -1000000000; dp[1][0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { for (int st : {0, 1, 2}) { int cur = dp[i][j][st]; if (cur == -1000000000) continue; char c = s[i - 1]; if (st == 0 || st == 2) { if (c == '1') { if (j < k) dp[i + 1][j + 1][st] = max(dp[i + 1][j + 1][st], cur + 1); } else if (c == '2') { dp[i + 1][j][st] = max(dp[i + 1][j][st], cur); if (j < k) dp[i + 1][j + 1][st] = max(dp[i + 1][j + 1][st], cur + 1); } else { dp[i + 1][j][st] = max(dp[i + 1][j][st], cur + 1); } if (st == 0 && i + 2 * t <= n) { int miss = mts[i + t - 1] - mts[i - 1]; if (j + miss <= k) { dp[i + t][j + miss][1] = max(dp[i + t][j + miss][1], cur); } } } else if (st == 1) { if (c == '1' || c == '2') { dp[i + 1][j][1] = max(dp[i + 1][j][1], cur); if (j < k) dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1], cur); } else { dp[i + 1][j][1] = max(dp[i + 1][j][1], cur); } if (i + t <= n + 1) { int miss = mts[i + t - 1] - mts[i - 1]; if (j + miss <= k) { dp[i + t][j + miss][2] = max(dp[i + t][j + miss][2], cur); } } } } } } int ans = -1; for (int j = 0; j <= k; j++) { ans = max(ans, dp[n + 1][j][0]); ans = max(ans, dp[n + 1][j][2]); } cout << (ans < 0 ? -1 : ans) << endl; } |