Codevs_1040_[NOIP2001]_統計單詞個數_(劃分型動态規劃)

描述

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上的資料好像有點問題,注意讀入.

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\n",dp[len][K]);
41 }
42 void init(){
43     scanf("%d%d\n",&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

轉載于:https://www.cnblogs.com/Sunnie69/p/5526564.html