P1026 统计单词个数

题目描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

输入输出格式

输入格式：

 

每组的第一行有二个正整数(p，k)

p表示字串的行数;

k表示分为k个部分。

接下来的p行，每行均有20个字符。

再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)

接下来的s行，每行均有一个单词。

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

1 3thisisabookyouareaoh4isaoksab

输出样例#1：

7

说明

this/isabookyoua/reaoh

 

【问题分析】

刚看到这个题目觉得很迷茫，没入手点但是突然看到了闪亮的突破口：题目中说this包含this和is 但不包含th这也就是说在一个串内对于一个固定了起点的单词只能用一次，即使他还可以构成别的单词但他还是用一次。比如：串：thisa

字典：this is th

串中有this  is  th这三个单词，但是对于this 和 th 只用一次，也就是说枚举一下构成单词的起点，只要以该起点的串中包含可以构成一个以该起点开头的单词，那么就说明这个串中多包含一个单词。

这样可以得出下面的结果：

枚举的起点                                   结论：

t                                            至少包含1个

h                                           至少包含1个

i                                            至少包含2个

s                                            至少包含2个

a                                            至少包含2个

考虑到这里，就有点眉目了。

题目中要将串分k个部分也就是说从一个点截断后一个单词就未必可以构成了。比如上例要分3个部分，合理的其中的一个部分至多有3个字母，这样this这个单词就构不成了。

要是分5个部分，那就连一个单词都构不成了。

这样就需要对上面做个改动，上面的只控制了起点，而在题目中还需要限制终点，分完几个部分后，每部分终点不同可以构成的单词就不同了。

这样就需要再枚举终点了。

设计一个二维数组sum[i,j]统计从i到j的串中包含的单词的个数

状态转移方程:

sum[i+1,j]+1            (s[i,j]中包含以s[i]开头的单词)

sum[i,j]= sum[i+1,j]               (与上面相反)

注：(1)这里枚举字符的起点的顺序是从尾到头的。

(2)有人把上面这次也看做是一次动态规划，但我觉得更准确的说是递推。

求出所有的sum还差一步，就是不同的划分方法显然结果是不一样的，但是对于求解的问题我们可以这样把原问题分解成子问题：求把一个串分成k部分的最多单词个数可以看做是先把串的最后一部分分出来，再把前面一部分分解成k-1个部分，显然决策就是找到一种划分的方法是前面的k-1部分的单词+最后一部分的单词最多。

显然这个问题满足最优化原理，那满不满足无后效性呢？

对于一个串分解出最后一部分在分解前面的那部分是根本就不会涉及分好的这部分，换句话说每次分解都会把串分解的更小，对于分解这个更小的串不会用到不属于这个小串的元素。这就满足无后效性。

具体求解过程：

设计一个状态opt[i,j]表示把从１到j的串分成i份可以得到最多的单词的个数。决策就是枚举分割点使当前这种分割方法可以获得最多的单词。

状态转移方程：opt[i,j]=max(opt[i-1,t]+sum[t+1,j])       (i<t<j)

边界条件：opt[1,i]=sum[1,i]                         (0<i<=L)

时间复杂度：状态数Ｏ（N²）*决策数O（N）=O（N³），空间复杂度：O（N²）。

 

sum[i][j]表示第i个字母到第j个字母一共可以形成多少个单词。

sum[i][j]=sum[i][-1]+（包含可以添加最后一个字母j的单词的总个数）。

注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置的参数表示以位置的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词。这样对于所有的不同个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的的值，这一部分的复杂度为O(wl2)。然后是计算把字串分为多个部分的过程中有什么单词可以留下。

 

1 #include 
     
         2 using namespace std;  3    4 const int maxn=250;  5 const int maxm=10;  6    7 string s;  8 int slen;  9 string words[maxm]; 10 int wordslen[maxm]; 11 int f[maxn][maxm]; 12 int sum[maxn][maxn]; 13 int n,k,m; 14   15 //读入数据  16 void init() 17 { 18     string tmp; 19     cin>>n>>k; 20     for (int i=1;i<=n;i++) 21     { 22         cin>>tmp; 23         s+=tmp; 24     } 25     slen=s.size(); 26     //读入字典  27     cin>>m; 28     for (int i=1;i<=m;i++) 29     { 30         cin>>words[i]; 31         wordslen[i]=words[i].size(); 32     } 33 } 34  35 //l头r尾  36 int add(int l,int r) 37 { 38     int ans=0; 39     //前面还有字符  40     if (r-1>=0) ans=sum[l][r-1]; 41     bool vis[maxn]={
   0}; 42     for (int i=1;i<=m;i++) 43     { 44         int qd=r-wordslen[i]+1; 45         if (qd
      
        %d\n",i,j,sum[i][j]); 74         } 75 } 76   77 void work() 78 { 79     for (int i=0;i<=slen-2;i++) 80         f[i][1]=sum[0][i]; 81     for (int i=0;i<=slen-2;i++) 82         for (int j=2;j<=min(k-1,i+1);j++) 83             for (int u=j-2;u<=i-1;u++) 84                 f[i][j]=max(f[i][j],f[u][j-1]+sum[u+1][i]); 85     int ans=0; 86     if (k==0) 87         ans=sum[0][slen-1]; 88     else 89         for (int i=k-1;i<=slen-2;i++) 90             ans=max(ans,f[i][k-1]+sum[i+1][slen-1]); 91     printf("%d\n",ans); 92 } 93   94 int main() 95 { 96     init(); 97     gsum(); 98     work(); 99     return 0;100 }