[题解]P3082 [USACO13MAR] Necklace G

P3082 [USACO13MAR] Necklace G

原问题等价于求 \(A\) 中最多能保留多少多少元素，使得 \(B\) 不是它的子串，再用 \(n\) 去减一下。

贪心地找 \(B\) 出现的位置统计是错误的。比如 aaabbbbbb ab 的答案是 \(3\)。

考虑 \(O(nm)\) 的 DP，令 \(f[i][j]\) 为 \(A\) 的前 \(i\) 个字符经过若干删除操作后，与 \(B\) 最长匹配长度为 \(j\) 时，最多保留多少个 \(A\) 中的元素。

则有转移：

• 删除 \(A_{i+1}\)：\(f[i][j]\to f[i+1][j]\)。
• 保留 \(A_{i+1}\)：\(f[i][j]+1\to f[k][j]\)。
  其中 \(k\) 是保留 \(A_{i+1}\) 后，新的匹配长度。

考虑如何预处理出这个 \(k\)，也即如何预处理出 \(p[i][j\in\{\texttt{A,B,\dots,Z}\}]\)，表示在已匹配 \(B[1\sim i]\) 的基础上，在主串末尾添加字符 \(j\)，新的匹配长度。

令 \(nxt[i]\) 为 \(B[1\sim i]\) 的最长 border，则有转移：

\[g[i][j]=\begin{cases} i+1&B_{i+1}=j\\ g[nxt[i]][j]&B_{i+1}\ne j \end{cases} \]

时间复杂度 \(O(n+m)\)。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e3+5,C=26;
string a,b;
int n,m,nxt[M],p[M][C],f[N][M],ans;
inline void chmx(int &x,int y){x=max(x,y);}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>a>>b;n=a.size(),m=b.size();a=' '+a,b=' '+b;for(int i=2,j=1;i<=m;i++){while(b[i]!=b[j]&&j>1) j=nxt[j-1]+1;if(b[i]==b[j]) nxt[i]=j++;}for(int i=0;i<m;i++){for(int j=0;j<26;j++){p[i][j]=(b[i+1]==j+'a'?i+1:p[nxt[i]][j]);}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){ chmx(f[i+1][j],f[i][j]);chmx(f[i+1][p[j][a[i+1]-'a']],f[i][j]+1);}}//注意f[][m]的状态既不能向后转移，也不能统计答案for(int i=0;i<m;i++) ans=max(ans,f[n][i]);cout<<n-ans<<"\n";return 0;
}