【NOIP2001】【Luogu1026】统计单词个数

problem

solution

codes

//just for test2
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n, m, x, d[210], f[210][50];
string s, w[20];
void pre(){
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= s.size(); i++){//枚举每个字母
        for(int j = 1; j <= x; j++){//枚举每个单词
            if(s.substr(i).find(w[j])==0){//如果存在i字母开头的单词
                d[i] = min(d[i], i+(int)w[j].size()-1);
            }
        }
    }
}
int main(){
    //input
    cin>>n>>m;
    s = " ";
    for(int i = 1; i <= n; i++){
        string t;  cin>>t;  s += t;
    }
    n *= 20;
    cin>>x;
    for(int i = 1; i <= x; i++)cin>>w[i];
    //预处理：得到c[i][j]为[i,j]中的最大单词数
    //预处理：得到d[i]为字母i开头的最短单词的结束位置(小贪心,每个字母只能按照第一个字母取一次)
    pre();
    //dp:f[i][j]为前i个字母划分成j段能得到的最大单词数
    //转移:f[i][j] = max{ f[k][j-1]+c[k+1][i] | k>=j&&k<i}
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int w = 0;
            for(int k = i; k >= j; k--){ //逆序覆盖
                if(d[k]<=i)w++; //w=[k,i]
                f[i][j] = max(f[i][j], f[k-1][j-1]+w);
                //if(d[k]<=i)w++;
            }
        }
    }

    /*
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++){
           int w=0;
           for(int k=i;k>=j;k--){
               if(d[k]<=i) w++;
               f[i][j]=max(f[i][j],f[k-1][j-1]+w);//w=(j,i)
           }
       }
       */
    cout<<f[n][m]<<"\n";
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80410050