USACO 3.2.2 : Stringsobits

问题描述

给定三个数$N$，$L$，$I$，要求找出所有长度为$N$且‘1’的个数不超过$L$的01字符串中的第$I$个（以字典序），例如$N=5$，$L=3$，$I=19$时，所求字符串为10011。数据范围为：
$1\leq N\leq 31, 1\leq L\leq N, 1\leq I\leq \sum_{i=0}^LC_N^i$。

问题解法

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

$$F[i][j] = F[i-1][j] + F[i-1][j-1] , 其中1\leq i,j\leq N$$
由此用动态规划的方法计算出所有$F[i][j]$：

  for (int i=0; i<=N; i++)
    F[0][i] = F[i][0] = 1;
  for (int i=1; i<=N; i++)
    for (int j=1; j<=L; j++)
      F[i][j] = F[i-1][j] + F[i-1][j-1];

注意到

• 对任意$I,L$，若$i$是最小的满足$F[i][L]\geq I$的$i$，则所求的字符串$S$的第$i-1$（从0开始计算）位必然是$1$, 因为若$S[i-1]=0$,则说明$F[i-1][L]\leq I$，这与之前对$i$的假设相矛盾。
• 当确定了$S[i-1]=1$后， 只需再往后数$I-F[i-1][L]$个满足$1$的个数不大于$L$的字符串即可找到所求的$S$（因为长度为$i$的字符串$1000\cdots 00$必然是满足条件的第$F[i-1][L]+1$个字符串）
• 当确定了$S[i-1]=1$后，只需在剩下的$0～i-2$位中搜索所有长度为$i-1$且$1$的个数不超过$L-1$的字符串。

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

  lower_bound = L;
  rest = I;
  while (rest > 1){
    for (int i=1; i<=N; i++)
      if (F[i][lower_bound] >= rest){
        S[i-1] = 1;
        rest -= F[i-1][lower_bound];
        lower_bound--;
        break;
      }
  }

另外要注意变量的类型，I和rest都应该是long以上类型。