我是靠谱客的博主 机智花生,这篇文章主要介绍Subsequences of Length Two【DP】,现在分享给大家,希望可以做个参考。

题目链接


  有一个长度为N的串S,有一个长度为2的串T,现在可以对S串做K次改变,最后使得T串在S串中的子序列出现次数最多。

  于是,涉及计数问题,就可以推一个DP来进行操作了,dp[i][j][k]表示处理到第i个位置,有j个t[0]时候,改变次数为k时候的最大值,然后分类讨论t[0]和t[1]的情况(相等、不想等)就可以推完这个dp方程了。

复制代码
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define pii pair<int, int> #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 2e2 + 5; int N, K; char s[maxN], t[3]; int dp[maxN][maxN][maxN]; inline void MAX(int &x, int y) { x = max(x, y); } int main() { scanf("%d%d", &N, &K); scanf("%s", s + 1); scanf("%s", t); for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) for(int k=0; k<=K; k++) dp[i][j][k] = -INF; dp[0][0][0] = 0; if(t[0] ^ t[1]) { for(int i=0; i<N; i++) { for(int j=0; j<=i; j++) { for(int k=0; k<=min(K, i); k++) { if(s[i + 1] == t[0]) { MAX(dp[i + 1][j + 1][k], dp[i][j][k]); MAX(dp[i + 1][j][k + 1], dp[i][j][k] + j); } else if(s[i + 1] == t[1]) { MAX(dp[i + 1][j][k], dp[i][j][k] + j); MAX(dp[i + 1][j + 1][k + 1], dp[i][j][k]); } else { MAX(dp[i + 1][j][k], dp[i][j][k]); MAX(dp[i + 1][j][k + 1], dp[i][j][k] + j); MAX(dp[i + 1][j + 1][k + 1], dp[i][j][k]); } } } } } else { for(int i=0; i<N; i++) { for(int j=0; j<=i; j++) { for(int k=0; k<=min(K, i); k++) { if(s[i + 1] == t[0]) { MAX(dp[i + 1][j + 1][k], dp[i][j][k] + j); } else { MAX(dp[i + 1][j][k], dp[i][j][k]); MAX(dp[i + 1][j + 1][k + 1], dp[i][j][k] + j); } } } } } int ans = 0; for(int i=0; i<=N; i++) for(int j=0; j<=K; j++) MAX(ans, dp[N][i][j]); printf("%dn", ans); return 0; } /* 4 2 abab ab ans:4 */

 

最后

以上就是机智花生最近收集整理的关于Subsequences of Length Two【DP】的全部内容,更多相关Subsequences内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(101)

评论列表共有 0 条评论

立即
投稿
返回
顶部