Luogu P1026 统计单词个数

YorkWu

May 28, 2019

1194 views

No comments

1113 words

OI 题目

这两天都忙得忘了写了。。。 今天把这几天做的好题都补一下吧。。。 [题目链接](https://www.luogu.org/problemnew/show/P1026 "题目链接")

* * *

老实说，这道题已经困扰我好几个月了，刚学dp就知道这道题，现在才做出来，所以准备写一下。。 题意大概就是给一个字符串，和一堆单词，问把这个字符串分成k段后，每段的单词数量的和的最大值是多少。 这道题用string的几个方法非常方便。 - <string>1.find(<string>2)在第一个字符串中查找字符串2，并返回第一个下标，如果不存在，返回1844674407370955161这是个什么鬼东西我也不知道。 - <string>.substr(x,len)取出字符串中以x开头长度为len的一个子字符串。 设计状态：$f\[i\]\[k\]$代表前i个字符分成k段的最大单词总数。 转移：$f\[i\]\[k\]=max(f\[i\]\[k\],f\[j\]\[k-1\]+sum\[j+1\]\[i\])$枚举断点j，$sum\[i\]\[j\]$代表原字符串从i到j的单词总数，先预处理一下。 剩下的看代码吧：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,k,m;
    string s,x;
    string d[8];
    int dl[8],sum[209][209];
    int dp[209][49];
    
    bool pd(int l,int r){
        string x=s.substr(l,r-l+1);
        for(int i=1;i<=m;i++){
            if(x.find(d[i])==0) return 1;
        }
        return 0;
    }
    
    int main(){
        cin>>n>>k;
        s="0";
        for(int i=1;i<=n;i++){
            cin>>x;
            s=s+x;
        }
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>d[i];
        }
        int len=s.length()-1;
        for(int i=len;i>=1;i--){
            for(int j=i;j>=1;j--){
                sum[j][i]=sum[j+1][i];
                if(pd(j,i)) sum[j][i]++;
            }
        }
        for(int i=1;i<=len;i++) dp[i][1]=sum[1][i];
        for(int q=1;q<=k;q++){
            for(int i=q+1;i<=len;i++){
                for(int j=q;j<i;j++){
                    dp[i][q]=max(dp[i][q],dp[j][q-1]+sum[j+1][i]);
                }
            }
        }
        cout<<dp[len][k];
        return 0;
    }
```

Last modification：March 14, 2020