[关闭]
@Junlier 2018-10-15T16:34:45.000000Z 字数 2390 阅读 1740

洛谷P3502 [POI2010]CHO-Hamsters感想及题解(图论+字符串+矩阵加速

题解
阅读体验:https://zybuluo.com/Junlier/note/1310683

扯闲谈

觉得这是道比较好的引导模型转换的题,就决定写一篇题解
即使我就是看的ZSY的,并且几乎写的一模一样(还是稍有不同的)
安利一发租酥雨的题解
原题地址:洛谷P3502 [POI2010]CHO-Hamsters

先理解题意

给出个字符串,让你用这个字符串拼接起来,使个字符串总的出现次数至少为,问拼接起来的字符串的最短长度是多少()

很容易想到一个

先用跑出每个字符串接在其他字符串后面的最小代价(增加的最短长度)记为数组

dp[k][i]表示已经出现了个字符串且最后一个字符串是号串的最短长度

显然直接就行了吧,放一段代码

  1. for(int i=1;i<=n;i++)
  2. dp[1][i]=len[i];
  3. for(int k=2;k<=m;k++)
  4. for(int i=1;i<=n;i++)
  5. for(int j=1;j<=n;j++)
  6. dp[k][i]=min(dp[k][i],dp[k-1][j]+dis[j][i]);

转换题型

看到上面那一段转移是不是神似?(好吧其实我已开始并不这么觉得
我们把每个字符串抽象成图上的一个点,原来求出的数组看做每对点之间的边(权)
那么是不是我们的问题就转化成了在图上跑个点的最短距离
很容易发现为什么上面的那么像了。。。

因为存在边界情况:所有字符作为开头时它的代价是len[i]
所以数组相对应有以下更新(新建一个号点表示开始节点):dis[0][i]=len[i],dis[i][0]=Inf

矩阵加速

不能完全叫矩阵,只是比较像
考虑到的每一次转移都是一遍(每一次转移都是一样的)
你想到了什么?矩阵快速幂优化
我们之前的矩阵优化都是通过矩阵之间的运算实现的
我们今天运用一个假的运算法则,它叫做矩阵运算法则
对于每一次的矩阵乘法改成一次运算,就可以顺利的把我们的级别的优化掉

也许你还是没有明白为什么可以把直接套进矩阵去优化
其实归根结底还是这个转移是没有变化的,且满足结合律
所以进行了很多遍的可以直接再和相“乘”(就是答案矩阵了)

代码

洛谷上不开还是会。。。

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rg register
  4. #define ldb double
  5. #define lst long long
  6. #define rgt register int
  7. #define N 250
  8. #define M 100050
  9. using namespace std;
  10. const lst Inf=1e18;
  11. il int read()
  12. {
  13. int s=0,m=0;char ch=getchar();
  14. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  15. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  16. return m?-s:s;
  17. }
  18. int n,m;
  19. int len[N];
  20. int Nxt[N][M];
  21. char S[N][M];
  22. lst Ans=Inf;
  23. struct Matrix{
  24. lst f[N][N];
  25. Matrix operator*(const Matrix K)const
  26. {
  27. Matrix mid;
  28. memset(mid.f,63,sizeof(mid.f));
  29. for(rgt k=0;k<=n;++k)
  30. for(rgt i=0;i<=n;++i)
  31. for(rgt j=0;j<=n;++j)
  32. mid.f[i][j]=min(mid.f[i][j],f[i][k]+K.f[k][j]);
  33. return mid;
  34. }
  35. }dis,ans;
  36. il void Get_dis()
  37. {
  38. for(rgt k=1;k<=n;++k)
  39. for(rgt i=2,j=0;i<=n;++i)
  40. {
  41. while(j&&S[k][i]!=S[k][j+1])j=Nxt[k][j];
  42. if(S[k][i]==S[k][j+1])++j;
  43. Nxt[k][i]=j;
  44. }
  45. //预处理KMP的Nxt[]
  46. dis.f[0][0]=Inf;
  47. for(rgt x=1;x<=n;++x)
  48. {
  49. dis.f[0][x]=len[x],dis.f[x][0]=Inf;
  50. for(rgt y=1;y<=n;++y)
  51. for(rgt i=2,j=0;i<=len[x];++i)
  52. {
  53. while(j&&S[y][j+1]!=S[x][i])j=Nxt[y][j];
  54. if(S[y][j+1]==S[x][i])++j;
  55. if(i==len[x])dis.f[x][y]=len[y]-j;
  56. }
  57. }//预处理两个字符串转化的最小长度
  58. }
  59. int main()
  60. {
  61. n=read(),m=read()-1;
  62. for(rgt i=1;i<=n;++i)
  63. scanf(" %s ",S[i]+1),len[i]=strlen(S[i]+1);
  64. Get_dis(),ans=dis;
  65. while(m)
  66. {
  67. if(m&1)ans=ans*dis;
  68. dis=dis*dis,m>>=1;
  69. }
  70. for(rgt i=1;i<=n;++i)
  71. Ans=min(Ans,ans.f[0][i]);
  72. printf("%lld\n",Ans);return 0;
  73. }

总结一下

模型转化还是比较重要的
考场上几次都没有想到
像遇到这种转化有代价,有要求最小代价的题目
就可以往最短路方面去转化
而遇到无法优化又有转移方程不变这种性质时
可以考虑矩阵快速幂优化

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注