「BZOJ1633」[Usaco2007 Feb] The Cow Lexicon 牛的词典
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
题解
从后往前递推
f[i]=f[i]+1
t为a串从i开始删掉t个才能与b[j]串匹配
f[i]=min{f[i+len+t]+t}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,f[305],L; char a[305],b[605][30]; inline int cal(int x,int len,int y) { int tot=0; int l1=x,l2=1; while(l1<=L) { if(a[l1]==b[y][l2])l2++; else tot++; if(l2==len+1)return tot; l1++; } return -1; } int main() { n=read();L=read(); scanf("%s",a+1); for(int i=1;i<=n;i++) scanf("%s",b[i]+1); f[L+1]=0; for(int i=L;i;i--) { f[i]=f[i+1]+1; for(int j=1;j<=n;j++) { int len=strlen(b[j]+1); int t=cal(i,len,j); if(t!=-1)f[i]=min(f[i],f[i+len+t]+t); } } printf("%d",f[1]); return 0; } |
Subscribe
计数器 9788179
OI 课件=>
OI 课件=>