POJ 3267 The Cow Lexicon 解题报告

POJ 3267 The Cow Lexicon

这题是一道DP问题,我的想法如下:

1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;

2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)

3.对deleteNum[pos]初始化后,可以对每个单词计算;

4.如果单词长度为lenWord且从当前位置(pos处)开始能够和单词匹配则:

deleteNum[pos]=min{deleteNum[pos],deleteNum[pos + 1] +1,deleteNum[pos + lenWord] + N}

其中第一个为原始值,第二个为未匹配时的值,第三个为匹配单词后的删除字符数,N为从pos匹配这个单词需要删除的字符数

5.如果不能匹配单词 deleteNum[pos]=min{deleteNum[pos],deleteNum[pos + 1] +1}解释如上;

6.deleteNum[0]则是要输出的数量

这是小弟个人意见,还望指正批评

代码如下:

#include<iostream>
#include<cstring>
using namespace std;
char words[601][30];
char str[301];
int deleteNum[301];
int minOfThree(int a,int b,int c);
int main()
{
    int w,l;
    cin>>w>>l;
    cin>>str;
    for(int i = 0 ; i < w ; i ++)
        scanf("%s",words[i]);
    int len = strlen(str);
    deleteNum[len] = 0;
    for(int i = len - 1 ; i >= 0 ; i --)
    {
        deleteNum[i] = 301;
        for(int j = 0 ; j < w ; j ++)
        {
            int isMatch = 0;
            int posWord = 0,posStr = i;
            while(words[j][posWord] && posStr < len)
            {
                if(words[j][posWord] == str[posStr])
                    posWord ++;
                posStr ++;
            }
            if(!words[j][posWord])
                deleteNum[i] = minOfThree(deleteNum[i],deleteNum[i + 1] + 1,deleteNum[posStr] + posStr - i - posWord);
            else
                deleteNum[i] = (deleteNum[i] < deleteNum[i + 1] + 1)?deleteNum[i]:deleteNum[i + 1] + 1;
        }
    }
    cout<<deleteNum[0];
    return 0;
}
int minOfThree(int a,int b,int c)
{
    return (a < b && a < c)?a:(b < c)?b:c;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

Java基础类String了解一下

当你路过一些商场或者地铁口的时候,有没有被千篇一律的"xx健身,了解一下" 所烦到。

23750
来自专栏互联网杂技

js的隐含参数(arguments,callee,caller)使用方法

在提到上述的概念之前,首先想说说javascript中函数的隐含参数: arguments arguments 该对象代表正在执行的函数和调用它的函数的参数。[...

37160
来自专栏我是攻城师

Java基础类String了解一下

当你路过一些商场或者地铁口的时候,有没有被千篇一律的"xx健身,了解一下" 所烦到。

12220
来自专栏cloudskyme

memset,memcpy,strcpy 的区别

一.函数原型    strcpy    extern char *strcpy(char *dest,char *src);    #include <stri...

420120
来自专栏夏时

PHP 特色:可变变量

15040
来自专栏应兆康的专栏

12步轻松搞定Python装饰器

Python里面的装饰器比较复杂,下面12步可以帮你你较好的理解Python中的装饰器 1. 函数 在python中,函数通过 def关键字、函数名和可选的参数...

354100
来自专栏JetpropelledSnake

Python学习笔记之Python正则表达式指南

正则表达式并不是Python的一部分。正则表达式是用于处理字符串的强大工具,拥有自己独特的语法以及一个独立的处理引擎,效率上可能不如str自带的方法,但功能十分...

21410
来自专栏每日一篇技术文章

Swift3.0 - 类和结构体的区别

结论: 在数据量比较大的排序中,结构体排序的速度比较慢,因为结构体是值类型,排序的时候,需要大量的赋值运算。而对象只需要交换地址即可。

10710
来自专栏从零开始的linux

Python数据类型

整型 a=10 b=0 b+=a c=-100 c-=a print (a, b ,c) print (dir(a)) print (abs(a)+abs(c)...

32040
来自专栏Web行业观察

说说这个this啊

上述代码中foo()不带任何修饰函数引用进行调用的,因此只能使用默认绑定,无法应用其他规则。 像这种独立函数调用是最常见的方式。值得一提的是在严格模式下,全局对...

13390

扫码关注云+社区

领取腾讯云代金券