F. Subsequences of Length Two
题意
给出一个长为n的串s(n<200)和一个只有两个字符的串t
一次修改可以将s串中的某个字符变成任意其他字符
要求在不超过k次修改的情况下 使s中等于t的子序列最多
题解
n<200可以考虑$n^3$ 的dp
最初想到dp(pos,修改成t[0]的次数,修改成t[1]的次数) dp值表示以pos未结尾有多少个子序列=t
后来根据题解设dp(pos,修改次数,到pos前s中有多少个字符=t[0])
同样dp值表示以pos未结尾有多少个子序列=t;
那么存在三种情况下的状态转移
e0=s[i]==t[0];
e1=s[i]==t[1];
- 不修改:dp(i+1,c,cnt+e0)=max(self,dp(i,c,cnt)+e1?cnt:0);
- 修改成t[0]：dp(i+1,c+1,cnt+1)=max(self,dp(i,c,cnt));
- 修改成t[1]：dp(i+1,c+1,cnt)=max(self,dp(i,c,cnt)+cnt);
可以将t[0]==t[1]的情况单独考虑 也可以直接在转移中处理
先将dp初始化为-inf 无法转移到的状态直接跳过
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e18+5;
const ll Mod=998857459;
ll dp[205][205][205];
int main() {
Turnoff;
int n,k;cin>>n>>k;
string s,t;cin>>s>>t;
ll ans=0;
if(t[0]==t[1]){
ll cnt=0;
for(int i=0;i<n;i++){
if(k&&s[i]!=t[0])cnt++,k--;
else if(s[i]==t[0])cnt++;
}
ans=cnt*(cnt-1)/2;
}
else{
for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)dp[i][j][k]=-Max;
dp[0][0][0]=0;
for(int i=0;i<n;i++){
for(int c=0;c<=min(k,i);c++){
for(int cnt=0;cnt<=i;cnt++){
if(dp[i][c][cnt]<0)continue;
int e0=s[i]==t[0],e1=s[i]==t[1];
dp[i+1][c][cnt+e0]=max(dp[i+1][c][cnt+e0],dp[i][c][cnt]+(e1?cnt:0));
if(c<k){
dp[i+1][c+1][cnt+1]=max(dp[i+1][c+1][cnt+1],dp[i][c][cnt]);
dp[i+1][c+1][cnt]=max(dp[i+1][c+1][cnt],dp[i][c][cnt]+cnt);
}
}
}
}
for(int c=0;c<=k;c++){
for(int cnt=0;cnt<=n;cnt++)ans=max(dp[n][c][cnt],ans);
}
}
cout<<ans<<endl;
}
|