Codevs_1040_[NOIP2001]_统计单词个数_(划分型动态规划)

摘要:
这个字母串需要分为k个部分,每个部分包含的单词总数最多(每个部分中包含的单词可以部分重叠。当选择一个单词时,其第一个字母不能再次使用。例如,thisis可以算作包含2个is)。这个单词在词典中给出,不超过6个单词。InputDescription InputDescription的第一行是一个正整数,表示有n组测试数据。每组的第一行有两个正整数(p,k)。p表示字符串中的行数;K被分成K个部分。接下来的p行各有20个字符。输出描述OutputDescription每行有一个整数,对应于每组测试数据的相应结果。
描述

http://codevs.cn/problem/1040/

Codevs_1017_乘积最大很像,都是划分型dp.

给出一个字符串和几个单词,要求将字符串划分成k段,在每一段中求共有多少单词(两个单词不能共享第一个字母),将每一段中的单词个数相加,求最大值.

1040 统计单词个数

2001年NOIP全国联赛提高组

时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一 定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一 个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)(管理员注:这里的不能再用指的是位 置,不是字母本身。比如thisis可以算做包含2个is)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。

输入描述 Input Description

第一行为一个正整数(0<n<=5)表示有n组测试数据
每组的第一行有二个正整数(p,k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行,每行均有20个字符。
再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)
接下来的s行,每行均有一个单词。

输出描述 Output Description

每行一个整数,分别对应每组测试数据的相应结果。

 

样例输入 Sample Input

1
1 3
thisisabookyouareaoh
4
is
a
ok
sab

样例输出 Sample Output

7

 
分析

用dp[i][k]表示将前i个字符划分成k段时的最优解(与乘积最大类似),那么有转移方程:

dp[i][k]=dp[j][k-1]+([j+1,i]中的单词个数).

这样就需要预处理每一个区间[i,j]中的单词个数.

对于区间[i,j],如果以str[i]开头有单词匹配,那么a[i][j]=a[i+1][j]+1.  否则a[i][j]=a[i+1][j].

写一个match函数来判断就好了.

 

注意:

1.codevs上的数据好像有点问题,注意读入.

 

Codevs_1040_[NOIP2001]_统计单词个数_(划分型动态规划)第1张Codevs_1040_[NOIP2001]_统计单词个数_(划分型动态规划)第2张
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxl=200+5,maxk=40+5,maxd=10;
 5 int n,p,K,s,len;
 6 int a[maxl][maxl],dp[maxl][maxl];
 7 char str[maxl],dic[maxd][maxl];
 8 
 9 bool match(int l,int r){
10     for(int i=1;i<=s;i++){
11         int len=strlen(dic[i]+1);
12         if(len>r-l+1) continue;
13         bool flag=true;
14         for(int j=1;j<=len;j++)
15             if(str[l-1+j]!=dic[i][j]) {
16                 flag=false;
17                 break;
18             }
19         if(flag) return true;
20     }
21     return false;
22 }
23 void pre(){
24     memset(a,0,sizeof a);
25     for(int i=1;i<=len;i++){
26         if(match(i,i)) a[i][i]=1;
27         for(int j=i-1;j;j--){
28             if(match(j,i)) a[j][i]=a[j+1][i]+1;
29             else a[j][i]=a[j+1][i];
30         }
31     }
32 }
33 void solve(){
34     pre();
35     for(int i=1;i<=len;i++) dp[i][1]=a[1][i];
36     for(int k=2;k<=K;k++)
37         for(int i=k;i<=len;i++)
38             for(int j=k-1;j<i;j++)
39                 dp[i][k]=max(dp[i][k],dp[j][k-1]+a[j+1][i]);
40     printf("%d
",dp[len][K]);
41 }
42 void init(){
43     scanf("%d%d
",&p,&K);
44     int id=0;
45     for(int i=1;i<=p;i++){
46         char c; c=getchar();
47         while(c>='a'&&c<='z'){
48             str[++id]=c;
49             c=getchar();
50         }
51     }
52     len=id;
53     scanf("%d",&s);
54     for(int i=1;i<=s;i++) scanf("%s",dic[i]+1);
55 }
56 int main(){
57     freopen("tjdcgs.in","r",stdin);
58     freopen("tjdcgs.out","w",stdout);
59     scanf("%d",&n);
60     while(n--){
61         init();
62         solve();
63     }
64     return 0;
65 }
View Code

免责声明:文章转载自《Codevs_1040_[NOIP2001]_统计单词个数_(划分型动态规划)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇分布式监控系统Zabbix--使用Grafana进行图形展示iptables.sh 初始化防火墙配置下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Python:对输入的单词进行字典序排序输出

题目描述:对输入的单词进行字典序排序输出,字典序定义: 1.单词中字母比较不区分大小写,两个单词先以第一个字母作为排序的基准,如果第一个字母相同,就用第二个字母为基准,如果第二个字母相同就以第三个字母为基准。依此类推,如果到某个字母不相同,字母顺序在前的那个单词顺序在前。2.当一个短单词和一个长单词的开头部分都相同(即短单词是长单词从首字母开始的一部分),...

中英文对照 —— 标点符号(punctuation)

有限的几个; What Are the Fourteen Punctuation Marks in English Grammar? period:句号;comma:逗号;冒号:colon;分号:semicolon; prime:上撇号,如数学分析中的一阶导数 f′(x) underscore:下划线;省略号:ellipsis; exclamatio...

一个有意思的英语发音辅助chrome插件

在这里下载:https://chrome.google.com/webstore/detail/jafbohhbdpejlcfpkbbpkegglokegjid 结合了特殊字符和规则来辅助发音,非常巧妙。 比如大家很容易搞不清重音的单词,在这个插件的帮助下就非常清楚了,如safari specific personnel这三个单词会变为如下三个,重音部分下...

英文文本的词频统计

英文文本由于不涉及分词问题,词频统计相对而言简单一些。以下是一个对英文文本进行词频统计的例子。其中的关键问题有:(1)英文中同时存在大小写,会干扰词频统计的结果,所以应将所有的英文字母转化为大写或小写;(2)英文单词可能被空格、标点或其他特殊符号分隔,因此应将这些特殊符号统一替换为空格;(3)根据空格对文本进行分隔;(4)用词典统计单词的出现次数;(5)由...

A Mini Locomotive(动态规划 01)

 /*  题意:选出3个连续的 数的个数  为K的区间,使他们的和最大 分析: dp[j][i]=max(dp[j-k][i-1]+value[j],dp[j-1][i]);   dp[j][i]:从j个数种选出i个连续区间  数值的最大和 value[j]:第j个区间内的数的和 和背包有点像,但要活用   */   #include <cstdio...

计算最长英语单词链

计算最长英语单词链的题目为: 大家经常玩成语接龙游戏,我们试一试英语的接龙吧:一个文本文件中有N 个不同的英语单词, 我们能否写一个程序,快速找出最长的能首尾相连的英语单词链,每个单词最多只能用一次。最长的定义是:最多单词数量,和单词中字母的数量无关。 统一输入文件名称:input1.txt, input2.txt 统一输出文件名称:output1.txt...