CodeVS/1040

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
统计单词个数	★★☆☆☆	答案正确	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; }