题解 CF1409F 【Subsequences of Length Two】

kradcigam

2020-09-05 15:48:38

Solution

看一下数据范围发现基本上标算应该是 $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; } ```