题解 P1026 【统计单词个数】

· · 题解

由于题目数据范围很很很小，所以可以有各种奇奇怪怪的方法可以水过去。

这里介绍两种比较适用（准确）的方法（正解）：

1.DP 考虑一个dp[i][j]表示前i个字母分成了j段时最大的单词数目，那么我们枚举一个位置p，在这个位置将字符串分成两段，那么这个

dp[i][j]=max(dp[p][j-1]+s[p+1][i])，我们定义s[i][j]表示在文本串（即文章）的第i个位置到第j个位置，以每个位置开头，以j为结尾，总共有多少单词。那么s数组可以用lenght(T)^3*number(单词)的效率预处理，然后dp数组可以用length(T)^2*k的效率直接搞出来。

DP的优化手段：如果单词数目比较多弄个Trie就可以把number的常数直接弄掉。同时s数组应该还可以用递推搞一搞，那么又可以把预处理的效率弄成length(T)^2。然后在实际操作中dp数组还可以用单调队列优化一下，那么就可以把一个length(T)给弄掉。

那么总效率就是O(length(T)^2+length(T)*k)

Trie基础传送门。

但是数据是非常小的，所以没必要这么麻烦。

2.贪心。我们考虑一下对分段为什么可以贪心。显然，如果我们将一个字符串分成了两段，那么对于每段的单词数是相互独立的，不会相互影响，符合无后效性。然后对于每次分段，实际上我们是把前面一段可以延伸到后面的单词数直接给减掉了，那么我们其实就可以把每次分段时每个位置被删掉会产生的负面贡献算出来，取个最小的，减掉，重复搞一搞，直到分成k段。这个我没打，具体可以参考楼下dalao们的。毕竟DP大法才是正道（手动滑稽）

参考代码（加了个Trie，所以代码长了点）：

#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=201;
int f[N][51],s[N][N],val[N*N],ch[N*N][26];
int NodeCnt=0,n,k,m,len;
string T,in;
void insert(string in){
    int u=0;
    for (int i=0;i<in.length();i++){
        int c=in[i]-'a';
        if (!ch[u][c])ch[u][c]=++NodeCnt;
        u=ch[u][c];
    }
    val[u]=1;
}
int query(int st,int en){
    int tot=0;
    for (int i=st;i<=en;i++){
        int u=0;
        for (int j=i;j<=en;j++){
            int c=T[j]-'a';
            if (!ch[u][c])break;
            u=ch[u][c];
            if (val[u]){tot++;break;}
        }
    }
    return tot;
}
int main(){
    ios::sync_with_stdio(false);
    while (cin>>n>>k){
        T="";
        for (int i=0;i<n;i++){
            cin>>in;
            T=T+in;
        }
        len=T.length();
        cin>>m; 
        for (int i=0;i<m;i++){
            cin>>in;
            insert(in);
        }
        for (int i=0;i<len;i++)
            for (int j=i;j<len;j++)
                s[i][j]=query(i,j);
        memset(f,~0x3f,sizeof(f));
        for (int i=0;i<len;i++)
            f[i][1]=s[0][i];
        for (int i=0;i<len;i++)
            for (int j=2;j<=k;j++)
                for (int p=0;p<i;p++)
                    f[i][j]=max(f[i][j],f[p][j-1]+s[p+1][i]);
        cout<<f[len-1][k];
    }
    return 0;
}
顺便提一句，此题数据非常水，我一开始把dp方程的写错了，同时把s数组只开到50，竟然过了4个点（一共才5个）！所以.....