题解：P3082 [USACO13MAR] Necklace G
ingo_dtw
·
·
题解
模拟赛考了这题，依旧被创飞。
看到题目我首先想到贪心有以下三种策略：
- 如果 M 的长度大于等于 3 那么直接删中间的。
- 如果 M 的长度等于 1 就直接删掉。
但是显然对于长度为 2 的时候，你不好判断怎么去删，是删前面的，还是删后面的。
观察一下题目的数据范围 N\le 10000，M\le 1000 考虑动态规划，我们设 dp_{i,j} 为考虑了 N 的前 i 位，M 的前 j 位，能剩余的字符串最长长度，那么关于 dp_{i,j} 的转移显然有：
-
如果 N_i 不选：
dp_{i,j}=dp_{i-1,j}
- 如果 N_i 选：
dp_{i,j}=\max\{dp_{i-1,j}+1,dp_{i,k}\}
好了，现在我们考虑怎么快速求出 $k$，一看到字符串匹配我们考虑 KMP，我们考虑预处理出一个 $nxtc_{i,c}$ 表示第 $i$ 个位置选 $N_i$ 能匹配到的 $M$ 的最大长度，于是考虑一下怎么转移，观察 KMP 的原理很容易想到：
- 如果 $M_{i+1}=c$ 那么：
$$nxtc_{i,c}=i+1$$
- 否则就是更具 $nxt_i$（注意没有第二维）匹配不到的转移选择次优的继续匹配，那么转移为：
$$nxt_{i,c}=nxtc_{nxt_i,c}$$
于是我们一遍跑 KMP 一遍预处理出 $nxtc$ 再用动态规划求出能剩余的字符串最长长度，则答案为：
$$n-\max\{dp_{n,i}\}$$（$n$ 为 $N$ 的长度）
时间复杂度：$\Theta(nm)$。
空间复杂度：$\Theta(nm)$。
:::success[[Ac Code](https://www.luogu.com.cn/record/243851942)]
```cpp line-numbers
#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long
#define rint register int
#define R register
#define _ read<int>()
template<class T>inline T read()
{
T r=0,f=1;R char c=gc();
while(!isdigit(c))
{
if(c=='-') f=-1;
c=gc();
}
while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
return f*r;
}
inline void out(rint x)
{
if(x<0) pc('-'),x=-x;
if(x<10) pc(x+'0');
else out(x/10),pc(x%10+'0');
}
const int MAXN=1e4+10,MAXM=1e3+10;
int dp[MAXN][MAXM],nxt[MAXM],nxtc[MAXM][30];
signed main()
{
string N,M;
cin>>N>>M;
rint n=N.size(),m=M.size();
N=' '+N,M=' '+M;
for(rint i=2,j=0;i<=m;i++)//对M跑一遍KMP
{
while(j>0&&M[i]!=M[j+1]) j=nxt[j];
if(M[i]==M[j+1]) j++;
nxt[i]=j;
}
for(rint i=0;i<=m;i++)//求出nxtc
{
for(rint j=0;j<26;j++)//枚举字符
{
nxtc[i][j]=(M[i+1]==j+'a')?i+1:nxtc[nxt[i]][j];
}
}
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(rint i=1;i<=n;i++)//dp
{
for(rint j=0;j<m;j++)//j=0是空串j=m不能转移
{
if(dp[i-1][j]<0) continue;
dp[i][j]=max(dp[i][j],dp[i-1][j]);
rint tmp=nxtc[j][N[i]-'a'];
if(tmp<m) dp[i][tmp]=max(dp[i-1][j]+1,dp[i][tmp]);
}
}
rint ans=0;
for(rint i=0;i<m;i++) ans=max(ans,dp[n][i]);
out(n-ans);
return 0;
}
```
:::