【洛谷1026】【NOIP2001】統計單詞個數

##題面

題目描述

給出一個長度不超過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 3

thisisabookyouareaoh

4

is

a

ok

sab

輸出樣例#1：

7

說明

this/isabookyoua/reaoh

題解

這是一道很容(keng)易(die)的DP題

我表示什麼也不想說

f[i][j]表示前i個字元分成j份的最大單詞數

那麼，我們不難退出遞推關系式

f[i][j]=max{f[k][j-1]+w[k+1][j]}(k< i)

其中w[i][j]表示i到j的單詞數

現在的問題就是如何求出w的值

方法很多

直接暴力就可以了

注意！暴力請不要使用substr截出子串再來判斷，否則會逾時

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
//f[i][j]表示前i個字母分成j段能夠得到的最大單詞個數 
//f[i][j]=max{f[k][j-1]+num[k+1][i]}
//num[i][j]表示i到j的單詞個數 
string ss;
string s;
int f[][],w[][];
int num[][];
bool vis[];
string a[];
int b[];
int n,p,k,l;
inline bool cmp(string a,string b)
{
       return a.length()<b.length();
}
int Count(string ss)
{
      int tot=;
      int ll=ss.length();
      bool fl=false;
      memset(vis,,sizeof(vis));
      for(int i=;i<=n;++i)//枚舉字典 
      {
             for(int j=;j<=ll-b[i];++j)//枚舉字元串 
               if(!vis[j])
               {
                    fl=false;
                    for(int k=;k<b[i];++k)
                      if(a[i][k]!=ss[k+j])
                      {
                           fl=true;
                           break;
                      }
                    if(!fl)
                    {
                          ++tot;
                          vis[j]=true;
                    }
               } 
      }
      return tot;
}
int main()
{
      cin>>p>>k;
      for(int i=;i<=p;++i)
      {
           cin>>ss;
           s=s+ss;
      }
      cin>>n;
      l=s.length();
      for(int i=;i<=n;++i)
           cin>>a[i];
      sort(&a[],&a[n+],cmp);
       for(int i=;i<=n;++i)
           b[i]=a[i].length();
      for(int i=;i<l;++i)
      {
        ss="";
        for(int j=i;j<l;++j)
        {
           ss+=s[j];
           w[i][j]=Count(ss);
        }
      } 
      for(int i=;i<l;++i)
         f[i][]=w[][i];
      //cout<<"K="<<k<<endl;
      for(int i=;i<l;++i)
        for(int j=;j<=min(i+,k);++j)
          for(int z=j-;z<i;++z)
            f[i][j]=max(f[z][j-]+w[z+][i],f[i][j]);
      cout<<f[l-][k]<<endl;
      return ;
}