CF1409F. Subsequences of Length Two

发表于 | 阅读数

给你两个字符串，分别是$𝑠,𝑡$ ，其中
$s$的长度为$n$，
$t$的长度为$2$。

你可以对字符串$s$ 做不超过$k$次操作，每一次操作可以选择字符串中任意一个字符然后将其变成任意一个字符。

设$dp[i][j][cnt]$表示字符串$s$ 的前$i$ 个字符中更改了$j$ 个字符以至于这$i$ 个字符中有$𝑐𝑛𝑡0$个 $𝑡0$字符时

转移就非常简单

  • 分$s[i]=t[1],s[i]=t[2],s[i]=t[1]=t[2],(s[i]!=t[1]\&s[i]!=t[2])$
  • 注意边界！！！！！！！！！

没有简化的代码很恶心。

代码 
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e2 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int dp[N][N][N];
char s[N], c[N];
int main()
{
    int n = read(), k = read();
    scanf("%s", s + 1);
    scanf("%s", c + 1);
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int t = 0; t <= n; t++)
                dp[i][j][t] = -1e9;
        }
    }
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            for (int t = 0; t <= i; t++)
            {
                dp[i][j][t] = dp[i - 1][j][t];
                if (s[i] == c[1])
                {
                    if (c[1] == c[2])
                    {
                        if (t >= 1)
                            dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j][t - 1] + t - 1);
                    }
                    else
                    {
                        if (t >= 1)
                            dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j][t - 1]);
                        if (j >= 1)
                            dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t] + t);
                    }
                }
                else if (s[i] == c[2])
                {

                    dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j][t] + t);
                    if (t >= 1 && j >= 1)
                        dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t - 1]);
                }
                if (c[1] == c[2])
                {
                    if (t >= 1 && j >= 1)
                        dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t - 1] + t - 1);
                }
                if (j >= 1)
                    dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t] + t);
                if (t >= 1 && j >= 1)
                    dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t - 1]);

                //cout << i << " " << j << " " << t << " " << dp[i][j][t] << endl;
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= k; j++)
    {
        for (int t = 0; t <= n; t++)
            ans = max(ans, dp[n][j][t]);
    }
    cout << ans << endl;
}