Stringsobits（DP）

Stringsobits
Kim Schrijvers

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits

INPUT FORMAT

A single line with three space separated integers: N, L, and I.

SAMPLE INPUT (file kimbits.in)

5 3 19

OUTPUT FORMAT

A single line containing the integer that represents the Ith element from the order set, as described.

SAMPLE OUTPUT (file kimbits.out)

10011

 

     题意：

     给出 N（1 ~ 31），L（1 ~ N），I，代表有一个 N 长度的 01 字符串，要求输出第 I 个满足 N 长度，其中里面 1 的个数不大于 L 的 01 字符串。

   

     思路：

     DP。设 dp [ i ] [ j ] 代表 i 长度时候，1的个数不大于 j 时候的字符串方法种数。所以：

     dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - 1 ] 。最后根据 dp [ i ] [ j ] 找出这个字符串，如果从右自左的第 K 位是1的话，必然满足 dp [ k - 1 ] [ j ] < I <= dp [ k ] [ j ]，所以不断判断是否 dp [ k - 1 ] [ j ] 是否大于 I 即可，如果满足，则 I -= dp [ k - 1 ] [ j ] ，且 --j。

 

     AC：

/*
ID:sum-g1
LANG:C++
PROG:kimbits
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

ll dp[50][50];

int main() {

    freopen("kimbits.in", "r", stdin);
    freopen("kimbits.out", "w", stdout);

    ll len, num, ans;
    scanf("%lld%lld%lld", &len, &num, &ans);

    for (ll i = 0; i <= len; ++i) {
        dp[i][0] = 1;
        dp[0][i] = 1;
    }

    for (ll i = 1; i <= len; ++i) {
        for (ll j = 1; j <= num; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }

    for (ll i = len; i >= 1; --i) {
        if (dp[i - 1][num] < ans) {
            ans -= dp[i - 1][num];
            --num;
            printf("1");
        } else printf("0");
    }

    printf("\n");

    return 0;
}