Description
没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音. 奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词的一个排列).
预处理所有位置前面所有字母出现离其最近的位置。DP。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,dp[310];
char mp[610][30],s[310];
inline int Min(int x,int y){return x<y ? x:y;}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);
for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
static int f[310][30],now[30];
for(int i=1;i<=m;++i)
{
for(int j=0;j<26;++j) f[i][j]=now[j];
now[s[i]-'a']=i;
}
for(int i=0;i<26;++i) f[m+1][i]=now[i];
int p;
for(int i=1;i<=m;++i)
{
dp[i]=i;
for(int j=1;j<=n;++j)
{
p=i+1;
for(int k=strlen(mp[j]+1);k;--k) p=f[p][mp[j][k]-'a'];
if(p) dp[i]=Min(dp[i],dp[p-1]+i-p+1-strlen(mp[j]+1));
}
}
printf("%d",dp[m]);
return 0;
}