查看CodeVS/1040的源代码 ←CodeVS/1040

[[分类:划分动态规划]]
==摘要==
{{信息题|统计单词个数|http://www.codevs.cn/problem/1040/|1|100|算法错误|60|time=2015-2-3 17:32:11}}
==题意==
将字母串分成k份，每份中包含的单词个数加起来总数最大(单词可以部分重叠，第一个字母位置不能再用)
==题解==
*黄金部分的最后一题做起来十分心酸（要不也不会被拖到最后做）。不过总算A了。
*其实这题可以看做是两重的动态规划，一层是统计，一层是划分。
===统计===
第一个小问题是如何求出第j~i位包含的单词总数，记作Count[j][i]。容易得到方程
 Count[j][i]=max
 {
    Count[j][i-1]+1 //如果以索引i结束的有一个单词//
    Count[j][i-1] //如果没有//
 };
<small>最初想法是采用前缀数组来计算，但是会遗漏某些重叠等情况，特别是某些单词是其它单词前缀的情况（直接去除较短了好像由于数据原因能A但是明显有反例）。误入歧途了很多次。</small>
===划分===
第二个小问题是求解。记f[i][k]为索引0~i处划分k次取得的最优解。枚举划分点，容易得到方程
    f[i][k]=max{f[j][k-1]+Count[j+1][i]};
（实际可以再省去一维空间，但是数据量较小，而且便于理解保留k维度）

==代码==
{{折叠|1040.cpp代码已折叠
|<pre>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int T,L,K,W,Count[300][3090],f[300][300];
string w[10]={},str;
int main()
{
    cin>>T;
    while(T--)
    {
        str="";
        cin>>L>>K;
        for(int i=1;i<=L;++i)
        {
            string s;
            cin>>s;
            str+=s;
        }
        cin>>W;
        for(int i=1;i<=W;++i)
            cin>>w[i];
        memset(Count,0,sizeof(Count));
        memset(f,-2,sizeof(f));
        for(int i=0;i<str.size();++i)
            for(int j=0;j<=i;++j)
            {
                if(i>=1&&i>j)
                    Count[j][i]=max(Count[j][i],Count[j][i-1]);
                for(int t=1;t<=W;++t)
                {
                    if(i-(signed)w[t].size()+1>=j)
                    {
                        if(str.substr(i-w[t].size()+1,w[t].size())==w[t])
                        {
                            if(i>j&&i>=1)
                                Count[j][i]=max(Count[j][i],Count[j][i-1]+1);
                            else
                                Count[j][i]=max(Count[j][i],1);
                        }
                    }
                }
                f[i][1]=Count[0][i];
            }
        for(int i=0;i<str.size();++i)
            for(int j=0;j<i;++j)
                for(int k=2;k<=K;++k)
                {
                    f[i][k]=max(f[i][k],f[j][k-1]+Count[j+1][i]);//fixed:f[j][k]->f[j][k-1]//
                }
        cout<<f[str.size()-1][K]<<endl;
    }
    return 0;
}

</pre>
|code1040}}