poj3267--The Cow Lexicon(dp:字符串组合)

2024-08-25 01:18

本文主要是介绍poj3267--The Cow Lexicon(dp:字符串组合),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

The Cow Lexicon
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 1: Two space-separated integers, respectively: W and L
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

Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer

Sample Output

2

Source

USACO 2007 February Silver
给出一个字符串,问最少去掉几个字符得到的序列是完全由给出的字典组成,字典在下面给出
根据问题,可以想到最后得到的字符串是字典组成的,那么组成这个字符串的单词在一开始就分散在给出的串中,我们要找的就是判断单词在字符串的位置。
dp[i]表示从头开始到第i个字符最少要消除多少个字符,
首先dp[0] = 1 ;
dp[i] = dp[i-1] , 匹配不到
dp[i] = dp[j] + k 出现字符串可以匹配到从j+1到i的字符串中,k = 从j+1到i完成匹配需要消除的字符。
一开始用最长公共子序列写,后来发现,在对dp[i]寻找从0到i有没有单词可以匹配的时候,要求,单词的最后一个单词一定和s[i]相同,不然那个单词在之前就已经匹配过了。
所以只要用普通的遍历就可以了。
PS:对于不知道开始或结束的位置的字符串判字串,用最长公共子序列,如果知道一个确定的位置,直接匹配。
#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;
}

这篇关于poj3267--The Cow Lexicon(dp:字符串组合)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104143

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3