[关闭]
@qqiseeu 2014-04-01T12:24:00.000000Z 字数 1026 阅读 3128

USACO 3.2.2 : Stringsobits

问题描述

给定三个数NLI,要求找出所有长度为N且‘1’的个数不超过L的01字符串中的第I个(以字典序),例如N=5L=3I=19时,所求字符串为10011。数据范围为:
1N31,1LN,1ILi=0CiN

问题解法

F[i][j]表示“长度为i1的个数不超过j的01字符串的个数”,则可以得到转移方程:

F[i][j]=F[i1][j]+F[i1][j1],1i,jN

由此用动态规划的方法计算出所有F[i][j]

  1. for (int i=0; i<=N; i++)
  2. F[0][i] = F[i][0] = 1;
  3. for (int i=1; i<=N; i++)
  4. for (int j=1; j<=L; j++)
  5. F[i][j] = F[i-1][j] + F[i-1][j-1];

注意到

综上得出核心部分的代码:

  1. lower_bound = L;
  2. rest = I;
  3. while (rest > 1){
  4. for (int i=1; i<=N; i++)
  5. if (F[i][lower_bound] >= rest){
  6. S[i-1] = 1;
  7. rest -= F[i-1][lower_bound];
  8. lower_bound--;
  9. break;
  10. }
  11. }

另外要注意变量的类型,Irest都应该是long以上类型。

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