P2875 [USACO07FEB] The Cow Lexicon S
GUO120822
·
·
题解
这真是道大水题。
拿道题之后，觉得这题肯定是动态规划。于是，就开始想状态。
想一想怎么转移。前面的变成牛语的字符串加上一个单词一定是一个合法牛语。所以我们只要看看结尾是哪个单词，然后配对。
```cpp
for (k=i;k>=1;k--)
{
if (a[k]==b[j][len]) len--;
else sum++;
if (!len) break;
}
```
$sum$ 表示配对失败的个数，
如果配对成功，那么就有 $dp_i=\max(dp_i,dp_{k-1}+sum)$。
$k-1$ 就是配对成功的开头的前一个。最后的结果就是 $dp_n$。
上代码！！
- 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=310,M=610;
int m,n,i,j,k,dp[N],len,sum;
char a[N],b[M][N];
int main()
{
scanf("%d%d%s",&m,&n,a+1);
for (i=1;i<=m;i++) scanf("%s",b[i]+1);
for (i=1;i<=n;i++)
{
dp[i]=i;
for (j=1;j<=m;j++)
{
sum=0;
len=strlen(b[j]+1);
for (k=i;k>=1;k--)
{
if (a[k]==b[j][len]) len--;
else sum++;
if (!len) break;
}
if (k) dp[i]=min(dp[i],dp[k-1]+sum);
}
}
printf("%d",dp[n]);
return 0;
}
```