题解 CF1409F 【Subsequences of Length Two】
kradcigam
2020-09-05 15:48:38
看一下数据范围发现基本上标算应该是 $O(n^3)$ 了、
我们考虑 $3$ 方的 $dp$。
首先 $\texttt{t}$ 的 $2$ 个字符相等的话,答案为
```cpp
int s=0;
for(int i=1;i<=n;i++)
if(a[i]==b[1])s++;
s=min(n,s+k);
int x=(s*(s-1)/2);
cout<<x;
```
代码的 $s$ 就是结果 $k$ 次操作,字符串 $\texttt{s}$ 里面最多有 $s$ 个 $\texttt{t}$ 的字符。
我们算一算,发现答案为
$$(s-1)+(s-2)+\cdots+1=\frac{s\times (s-1)}{2}$$
换个角度也可以
$$\begin{pmatrix} s \\ 2 \end{pmatrix} = \frac{s\times (s-1)}{2} $$
那么剩下的情况就是这 $2$ 个字符不同了。
我们想一想,其实,字符串 $\texttt{s}$ 里有多少个字符串 $\texttt{t}$ 就直接看字符串 $\texttt{s}$ 里**每个字符 $\texttt{t}_2$ 前 $\texttt{t}_1$ 的个数。**
举个例子:
```cpp
aababccabb
ab
```
里有多少个子子序列 $\texttt{t}$ 呢
| 字符标号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 字符 | a | a | b | a | b | c | c | a | b | b |
| 前面 $a$ 的个数 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
| $ans$ | 0 | 0 | 2 | 2 | 5 | 5 | 5 | 5 | 9 | 13 |
不难发现有 $13$ 个。
我们用 $f_{i,j,k}$ 来 $dp$。
它的意义:
- $i$ 就对应上面的字符编号
- $j$ 指的是前 $i$ 个字符修改了多少个
- $k$ 对应上面的前面 $a$ 的个数
还有一个非常重要的东西,对于一个字符,要么将它修改为 $\texttt{t}_2$、要么将它修改为 $\texttt{t}_1$,要么不修改。
这样我们的状态转移方程就好写了
分别对应不修改
$$f_{i,j,k}=f_{i-1,j,k}$$
修改为 $\texttt{t}_1$
- 如果这个字符本来为 $\texttt{t}_1$,则
$$f_{i,j,k}=f_{i-1,j,k-1}$$
- 否则
$$f_{i,j,k}=f_{i-1,j-1,k-1}$$
修改为 $\texttt{t}_2$
- 如果这个字符本来为 $\texttt{t}_2$,则
$$f_{i,j,k}=f_{i-1,j,k}+k$$
- 否则
$$f_{i,j,k}=f_{i-1,j-1,k}+k$$
初始化的话先全部赋值为无穷小,再将 $f_{0,i,0}$ 赋值为 $0$(这里 $i\in (1,k)$)
```cpp
// Problem: F. Subsequences of Length Two
// Contest: Codeforces - Codeforces Round #667 (Div. 3)
// URL: https://codeforces.ml/contest/1409/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
int n,k,f[210][210][210];
string a,b;
signed main(){
memset(f,128,sizeof(f));
read(n);read(k);
cin>>a>>b;
a=' '+a;b=' '+b;
if(b[1]==b[2]){
int s=0;
for(int i=1;i<=n;i++)
if(a[i]==b[1])s++;
s=min(n,s+k);
int x=(s*(s-1)/2);
cout<<x;
return 0;
}
for(int i=0;i<=k;i++)f[0][i][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
for(int l=0;l<=i;l++){
f[i][j][l]=f[i-1][j][l];
if(a[i]==b[1])f[i][j][l]=max(f[i][j][l],f[i-1][j][l-1]);
else if(j)f[i][j][l]=max(f[i][j][l],f[i-1][j-1][l-1]);
if(a[i]==b[2])f[i][j][l]=max(f[i][j][l],f[i-1][j][l]+l);
else if(j)f[i][j][l]=max(f[i][j][l],f[i-1][j-1][l]+l);
}
int ans=0;
for(int i=0;i<=n;i++)ans=max(ans,f[n][k][i]);
cout<<ans;
return 0;
}
```