| 题目名称 | 174. [USACO Feb07] 奶牛词典 |
|---|---|
| 输入输出 | lexicon.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：66， 提交：161， 通过率：40.99% | ||||
 一個人的雨 |
100 | 0.014 s | 0.40 MiB | C++ |
 落尘 |
100 | 0.015 s | 0.40 MiB | C++ |
 天亮说晚安· |
100 | 0.025 s | 0.68 MiB | C++ |
 呵呵酵母菌 |
100 | 0.030 s | 0.72 MiB | C++ |
 Hzoi_moyi |
100 | 0.035 s | 0.68 MiB | C++ |
 Hzoi_QTY |
100 | 0.035 s | 1.73 MiB | C++ |
 Hallmeow |
100 | 0.044 s | 0.34 MiB | C++ |
 A_LEAF |
100 | 0.044 s | 0.40 MiB | C++ |
 Dissolute丶Tokgo |
100 | 0.048 s | 0.33 MiB | C++ |
 0_0 |
100 | 0.049 s | 0.33 MiB | C++ |
| 关于 奶牛词典 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
手贱1打成0 居然还能40分
 | ||||
 Hzoi_Mafia
2017-05-31 11:24
5楼
| ||||
|
啦啦啦~朴素DP加个剪枝给撸过去了
    Hzoi_Maple
2017-05-31 11:22
4楼
| ||||
|
查字典卡成
 2333 Hzoi_Mafia
2017-05-31 10:54
3楼
| ||||
|
水DP
 Makazeu
2012-11-06 12:15
2楼
| ||||
|
状态不好,效率低
 QhelDIV
2012-11-05 22:18
1楼
| ||||
~玖湫~
译: zqzas
【题目描述】
没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她 说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音.
奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词 的一个排列).
【输入格式】
第1行:两个用空格隔开的整数,W和L.
第2行:一个长度为L的字符串,表示收到的信息.
第3行至第W+2行:奶牛的字典,每行一个词.
【输出格式】
一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".
【输入样例】
6 10 browndcodw cow milk white black brown farmer
【输出样例】
2