CF 1409F. Subsequences of Length Two (字符串+DP)
题目链接：传送门
题目思路：
字符串t 一共有两种情况：
1） t[1]==t[2]
直接统计s[i]==t[1]的个数，剩余的不相等的字符作修改，最后利用等差数列求和公式求出答案。
2） t[1] !=t[2]
定义 dp[i][j][k]， 表示s串 前i个字符 ，j次修改，使得有k个字符 == t[1] ,
对于第i个字符，dp一共有三种转移方式： 不修改；修改成t1；修改成t2；
不修改：dp[i][j][k] = dp[i-1][j][k]
修改为t1: s[i]==t1 , dp[i][j][k] = dp[i-1][j][k-1] ; s[i]!=t1 , dp[i][j][k] = dp[i-1][j-1][k-1];
修改为t2: s[i]==t2 , dp[i][j][k] = dp[i-1][j][k] + k ; s[i]!=t2 , dp[i][j][k] = dp[i-1][j-1][k] + k;
对于三种转移取 MAX
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=2e2+5; 5 const int inf=0x3f3f3f3f; 6 LL read() 7 { 8 LL x=0,f=1; 9 char ch=getchar(); 10 while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } 11 while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } 12 return f*x; 13 } 14 LL dp[N][N][N]; 15 char s[N],t[N]; 16 int main() 17 { 18 LL n=read(),m=read(); 19 scanf("%s%s",s+1,t+1); 20 if(t[1]==t[2]) 21 { 22 LL ans=0; 23 for(int i=1;i<=n;i++) 24 if(s[i]==t[1]) ans++; 25 ans=min(n,ans+m); 26 return 0*printf("%lld ",ans*(ans-1)/2); 27 } 28 memset(dp,-1,sizeof(dp)); 29 for(int i=0;i<=m;i++) dp[0][i][0]=0; 30 for(int i=1;i<=n;i++) 31 { 32 for(int j=0;j<=m;j++) 33 for(int k=0;k<=i;k++) 34 { 35 dp[i][j][k]=dp[i-1][j][k]; 36 if(s[i]==t[1]) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]); 37 else if(j) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]); 38 if(s[i]==t[2]){ if(dp[i-1][j][k]!=-1) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+k); } 39 else if(j&&dp[i-1][j-1][k]!=-1) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+k); 40 } 41 } 42 LL ans=0; 43 for(int i=0;i<=n;i++) ans=max(ans,dp[n][m][i]); 44 printf("%lld ",ans); 45 return 0; 46 }