（以“分类:划分动态规划 ==摘要== {{信息题|统计单词个数|http://www.codevs.cn/problem/1040/|1|100|算法错误|60|time=2015-2-3 17:32:11}} ==题意== ...”为内容创建页面） |
小 （→摘要： 改难度） |
||
| （未显示1个用户的1个中间版本） | |||
| 第1行： | 第1行： | ||
[[分类:划分动态规划]] | [[分类:划分动态规划]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|统计单词个数|http://www.codevs.cn/problem/1040/| | + | {{信息题|统计单词个数|http://www.codevs.cn/problem/1040/|2|100|算法错误|60|time=2015-2-3 17:32:11}} |
| + | |||
==题意== | ==题意== | ||
将字母串分成k份，每份中包含的单词个数加起来总数最大(单词可以部分重叠，第一个字母位置不能再用) | 将字母串分成k份，每份中包含的单词个数加起来总数最大(单词可以部分重叠，第一个字母位置不能再用) | ||
| 第15行： | 第16行： | ||
}; | }; | ||
<small>最初想法是采用前缀数组来计算，但是会遗漏某些重叠等情况，特别是某些单词是其它单词前缀的情况（直接去除较短了好像由于数据原因能A但是明显有反例）。误入歧途了很多次。</small> | <small>最初想法是采用前缀数组来计算，但是会遗漏某些重叠等情况，特别是某些单词是其它单词前缀的情况（直接去除较短了好像由于数据原因能A但是明显有反例）。误入歧途了很多次。</small> | ||
| − | + | ===划分=== | |
第二个小问题是求解。记f[i][k]为索引0~i处划分k次取得的最优解。枚举划分点，容易得到方程 | 第二个小问题是求解。记f[i][k]为索引0~i处划分k次取得的最优解。枚举划分点，容易得到方程 | ||
f[i][k]=max{f[j][k-1]+Count[j+1][i]}; | f[i][k]=max{f[j][k-1]+Count[j+1][i]}; | ||
（实际可以再省去一维空间，但是数据量较小，而且便于理解保留k维度） | （实际可以再省去一维空间，但是数据量较小，而且便于理解保留k维度） | ||
| + | |||
==代码== | ==代码== | ||
{{折叠|1040.cpp代码已折叠 | {{折叠|1040.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 统计单词个数 | ★★☆☆☆ | 答案正确 | 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;
}
|