Logo CloudLunar

“CodeVS/1040”的版本间的差异

（以“分类:划分动态规划 ==摘要== {{信息题|统计单词个数|http://www.codevs.cn/problem/1040/|1|100|算法错误|60|time=2015-2-3 17:32:11}} ==题意== ...”为内容创建页面）
 
小 （→‎统计： 排版）
第15行： 第15行：
 
  };
 
  };
 
<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代码已折叠

2015年2月3日 (二) 17:56的版本

摘要

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

题意

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

题解

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

统计

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

显示/移除行号
  1. Count[j][i]=max
  2. {
  3.    Count[j][i-1]+1 //如果以索引i结束的有一个单词//
  4.    Count[j][i-1] //如果没有//
  5. };

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

划分

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

显示/移除行号
  1.    f[i][k]=max{f[j][k-1]+Count[j+1][i]};

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

代码

1040.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<iostream>
  2. #include<cstring>
  3. #include<string>
  4. using namespace std;
  5. int T,L,K,W,Count[300][3090],f[300][300];
  6. string w[10]={},str;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--)
  11.     {
  12.         str="";
  13.         cin>>L>>K;
  14.         for(int i=1;i<=L;++i)
  15.         {
  16.             string s;
  17.             cin>>s;
  18.             str+=s;
  19.         }
  20.         cin>>W;
  21.         for(int i=1;i<=W;++i)
  22.             cin>>w[i];
  23.         memset(Count,0,sizeof(Count));
  24.         memset(f,-2,sizeof(f));
  25.         for(int i=0;i<str.size();++i)
  26.             for(int j=0;j<=i;++j)
  27.             {
  28.                 if(i>=1&&i>j)
  29.                     Count[j][i]=max(Count[j][i],Count[j][i-1]);
  30.                 for(int t=1;t<=W;++t)
  31.                 {
  32.                     if(i-(signed)w[t].size()+1>=j)
  33.                     {
  34.                         if(str.substr(i-w[t].size()+1,w[t].size())==w[t])
  35.                         {
  36.                             if(i>j&&i>=1)
  37.                                 Count[j][i]=max(Count[j][i],Count[j][i-1]+1);
  38.                             else
  39.                                 Count[j][i]=max(Count[j][i],1);
  40.                         }
  41.                     }
  42.                 }
  43.                 f[i][1]=Count[0][i];
  44.             }
  45.         for(int i=0;i<str.size();++i)
  46.             for(int j=0;j<i;++j)
  47.                 for(int k=2;k<=K;++k)
  48.                 {
  49.                     f[i][k]=max(f[i][k],f[j][k-1]+Count[j+1][i]);//fixed:f[j][k]->f[j][k-1]//
  50.                 }
  51.         cout<<f[str.size()-1][K]<<endl;
  52.     }
  53.     return 0;
  54. }
  55.  
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/1040&oldid=1024”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]