| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 统计单词个数 | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-3 17:32:11 | 算法错误（60） |
将字母串分成k份，每份中包含的单词个数加起来总数最大(单词可以部分重叠，第一个字母位置不能再用)
第一个小问题是如何求出第j~i位包含的单词总数，记作Count[j][i]。容易得到方程
CloudLunarCount[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;
}
|