poj3267--The Cow Lexicon(dp:字符串组合)
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 8211 | Accepted: 3864 |
Description
Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not
very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.
The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular,
they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.
Input
Line 2: L characters (followed by a newline, of course): the received message
Lines 3..W+2: The cows' dictionary, one word per line
Output
Sample Input
6 10
browndcodw
cow
milk
white
black
brown
farmer
Sample Output
2
Source
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int l ;
char s[30] ;
} p[700];
int dp[400];
char s[400] ;
int cmp(node a,node b)
{
return a.l < b.l ;
}
int main()
{
int i , j , n , l ;
while( scanf("%d %d", &n, &l)!=EOF)
{
scanf("%s", s);
for(i = 0 ; i < n ; i++)
{
scanf("%s", p[i].s);
p[i].l = strlen(p[i].s);
}
sort(p,p+n,cmp);
memset(dp,0,sizeof(dp));
dp[0] = 1 ;
for(i = 0 ; i < l ; i++)
{
if(i)
dp[i] = dp[i-1]+1 ;
for( j = 0 ; p[j].l <= i+1 ; j++)
{
int k1 = i , k2 = p[j].l-1 ;
if( s[k1] != p[j].s[k2] ) continue ;
while( k1 >= 0 && k2 >= 0 )
{
if( s[k1] == p[j].s[k2] )
{
k1-- ;
k2-- ;
}
else
k1-- ;
}
if( k2 == -1 )
{
dp[i] = min( dp[i],dp[k1]+i-k1-p[j].l );
}
}
}
printf("%d\n", dp[l-1]);
}
return 0;
}
最新文章
- js限制输入框只能输入数字
- Markdown入门基础
- java生成竖排文字图片
- java中方法的参数传递机制(值传递还是引用传递)
- MySQL之学生名次问题
- 11 个最佳 jQuery 滚动条插件
- 关于Androdi中SQLITE 3采用GBK编码存储,数据库中文乱码问题。
- BAE 环境下配置 struts2 + spring + hibernate(SSH)(二)struts2
- UIWebvView 解决onClick 延迟相应问题
- 【Java疑难杂症】有return的情况下try catch finally的执行顺序
- StringMVC @RequestMapping method属性
- AngularJS学习之旅—AngularJS 过滤器(七)
- Codeforces Round #495 (Div. 2) C. Sonya and Robots
- 关于python中的类方法(classmethod)和静态方法(staticmethod)
- php null
- ASP.NET CORE的H5上传
- gispro设置标注属性字体样式设置
- Python进阶【第三篇】Python中的基本数据类型
- linux 文件管理操作入门
- Numpy函数库基础