题解：P1026 [NOIP 2001 提高组] 统计单词个数

· · 题解

废话不多说，多说的不是废话，我们直接进入正题。

题目简化： 没什么好简化的，自己看题目去。

首先，让我们来回顾一下区间 DP 的知识。

区间 DP，即对一个区间内的元素进行合并或拆分的操作，在满足要求的前提下求出最小（或最大）代价。

好，让我们回到这道题上。题目中的“分割成 k 个部分”这句话，看上去不就很像一个区间 DP 吗？因为这是分割型 DP（具体定义详见这篇文章），所以我们定义的 DP 状态 dp_{i,j} 表示前 i 个字符分割成 j 个区间的最大个数，那么状态转移方程就可以写成这样：

dp_{i,j}=\max^i_j\{dp_{k-1,j-1}+a_{k,i}\}

其中 a_{i,j} 表示从第 i 个字符到第 j 个字符中的单词数。

现在我们就需要考虑一下这个 a_{i,j} 怎么求了。

我这里提供一种思路：我们可以把 a_{i,j} 也当做一个 DP，那么 a_{i,j} 首先就肯定要继承上一个状态，即 a_{i,j}=a_{i,j-1}，然后我们看看当前从 i 到 j 这个字符串中有没有单词。

但我相信很多人都能看出来其中的问题：这个字符串里的同一个单词在上次和这次会被重复计算。我又想到了一个办法：我只需要找后几个字母构成的“词”是不是单词就行了，而这个“词”的长度就是单词的长度。

由于本人怕跑循环会 TLE，但又不会哈希，于是决定用 STL，不会 STL 中的 string 的 find 的用法的同学见这篇文章。

提交记录，完美 AC。

代码：

#include<bits/stdc++.h>
#define int long long
#define npos string::npos
using namespace std;
int n,m,kk,vis[206],siz[16],a[206][206],dp[206][46];
string s,ss[16];
signed main()
{
    s+=" ";
    cin>>m>>kk;
    while(m--)
    {
        string t="";
        cin>>t;
        s+=t;
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>ss[i];
        siz[i]=ss[i].size();
    }
    n=s.size()-1;//这里注意！！！
    for(int i=1;i<=n;i++)
    {
        string t="";
        memset(vis,0,sizeof(vis));
        for(int j=i;j<=n;j++)
        {
            a[i][j]=a[i][j-1];
            t+=s[j];
            int l=t.size();
            for(int k=1;k<=m;k++)
            {
                if(l-siz[k]<0||vis[l-siz[k]])
                {
                    continue;
                }
                if(t.rfind(ss[k])==l-siz[k])//详见上面的文章
                {
                    a[i][j]++;
                    vis[l-siz[k]]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=min(i,kk);j++)
        {
            for(int k=j;k<=i;k++)
            {
                dp[i][j]=max(dp[i][j],dp[k-1][j-1]+a[k][i]);
            }
        }
    }
    cout<<dp[n][kk];
    return 0;
}