codevs 1779 单词的划分

1779 单词的划分

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

Problem有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。Output一个整数，表示字符串可以被划分成的最少的单词数。

应该加上一个前提题目中提供的字符串肯定能被划分，否则输出增加判断语句。

输入描述 Input Description

从文本文件word.in中读入数据。第一行，一个字符串。(字符串的长度不超过100)，第二行一个整数n，表示单词的个数。(n<=100)，第3~n+2行，每行列出一个单词。

输出描述 Output Description

一个整数，表示字符串可以被划分成的最少的单词数。

样例输入 Sample Input

realityour
5
real
reality
it
your
our

样例输出 Sample Output

数据范围及提示 Data Size & Hint

(原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用)

 1 /*基本思路：p[i][j]数组储存着从i--j这个区间内，能不能划分为一个单词，是1，否则一个大数
 2            DP方程：f[i]=min(f[i],f[t]+p[t+1][i]);f[i]储存着到1---i为止可以   划分的单词的最小数目，
 3            t从0到i--1枚举，f[t]前t位，p数组表示吧t+1--i当做一个单词 
 4            
 5   注意：substr函数的使用a.substr(i,l)，表示把a字符串从第i位开始，切割l位形成的一个字符串 
 6 */
 7 #include<iostream>
 8 using namespace std;
 9 #include<cstdio>
10 #include<string>
11 #include<cstring>
12 #define N 101
13 int p[N][N],f[N],lena;
14 string a,b[N];
15 int n;
16 void input()
17 {
18     cin>>a;
19     scanf("%d",&n);
20     for(int i=1;i<=n;++i)
21     cin>>b[i];
22 }
23 void ZB()
24 {
25 /*    memset(p,99,sizeof(p));这一句赋值超大数是不对的，DP方程中会使int类型越界，所以题目中赋值最大根据题意，不要出现越界的情况，这个题p[][]=1000就足够大了*/
26     lena=a.length();
27     for(int i=0;i<lena;++i)
28       for(int j=i;j<lena;++j)
29       {
30           int l=j-i+1;
31           for(int k=1;k<=n;++k)
32           if(a.substr(i,l)==b[k])
33           {
34               p[i][j]=1;
35               break;
36           }
37         else {
38             p[i][j]=1001;
39         } 
40       }
41 }
42 void DP()
43 {
44     for(int i=0;i<lena;++i)
45     f[i]=p[0][i];
46     for(int i=1;i<lena;++i)
47        for(int t=0;t<=i-1;++t)
48        f[i]=min(f[i],f[t]+p[t+1][i]);
49 }
50 int main()
51 {
52     input();
53     ZB();
54     DP();
55     cout<<f[lena-1];
56     return 0;
57  }

View Code