摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
统计单词个数 ★★☆☆☆ 答案正确 100 2015-2-3 17:32:11 算法错误(60)


题意

将字母串分成k份,每份中包含的单词个数加起来总数最大(单词可以部分重叠,第一个字母位置不能再用)

题解

  • 黄金部分的最后一题做起来十分心酸(要不也不会被拖到最后做)。不过总算A了。
  • 其实这题可以看做是两重的动态规划,一层是统计,一层是划分。

统计

第一个小问题是如何求出第j~i位包含的单词总数,记作Count[j][i]。容易得到方程

Count[j][i]=max
{
   Count[j][i-1]+1 //如果以索引i结束的有一个单词//
   Count[j][i-1] //如果没有//
};

最初想法是采用前缀数组来计算,但是会遗漏某些重叠等情况,特别是某些单词是其它单词前缀的情况(直接去除较短了好像由于数据原因能A但是明显有反例)。误入歧途了很多次。

划分

第二个小问题是求解。记f[i][k]为索引0~i处划分k次取得的最优解。枚举划分点,容易得到方程

   f[i][k]=max{f[j][k-1]+Count[j+1][i]};

(实际可以再省去一维空间,但是数据量较小,而且便于理解保留k维度)

代码

1040.cpp代码已折叠
展开折叠内容
#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;
}

著作权声明[编辑]

关于[编辑]