1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 398 Solved: 213
[Submit][Status]
Description
没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音. 奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L
(2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词的一个排列).
Input
第1行:两个用空格隔开的整数,W和L.
第2行:一个长度为L的字符串,表示收到的信息. 第3行至第W+2行:奶牛的字典,每行一个词.
Output
唯一一行:一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".
Sample Input
6 10
browndcodw
cow
milk
white
black
brown
farmer
browndcodw
cow
milk
white
black
brown
farmer
Sample Output
2
仔细想一想为什么要倒推
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
int W,L;
char s[301];
char str[601][26];
int dp[301];
int len[301];
/////////////////////////////////////////////////
int cal(int pos,int n)
{
int cur=1;
int ret=0;
while(1)
{
while(pos<=L && cur<= len[n] && str[n][cur]==s[pos]) pos++,cur++;
if(cur>len[n]) return ret;
pos++;ret++;
if(pos>L) return -1;
}
return ret;
}
/////////////////////////////////////////////////
void input()
{
scanf("%d%d",&W,&L);
scanf("%s",s+1);
rep(i,1,W)
{
scanf("%s",str[i]+1);
len[i]=strlen(str[i]+1);
}
}
void solve()
{
///////////////////init///////////////////
////////////////calculate////////////////
per(i,L,1)
{
dp[i]=dp[i+1]+1;
rep(j,1,W) if(s[i]==str[j][1])
{
int t=cal(i,j);
if(t==-1) continue;
dp[i]=min(dp[i],dp[i+len[j]+t]+t);
}
//printf("dp[%d]=%d\n",i,dp[i]);
}
/////////////////output/////////////////
printf("%d\n",dp[1]);
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("std.out","w",stdout);
#endif
input();
solve();
#ifdef _TEST
for(;;);
#endif
return 0;
}