POJ-3252 Round Numbers 비트 DP

앞에서 조합수학으로 이 문제를 쓴 것은 경계 조건에 의해 머리가 어지럽고 어지럽다. 여기는 바로 위치DP를 누르고 매번 dfs가 0과 1의 개수를 전달하는 두 파라미터를 내려가면 된다.
코드는 다음과 같습니다.

#include <cstdlib>

#include <cstdio>

#include <cstring>

using namespace std;



int a, b, bit[35], dp[35][35][35];



int dfs(int pos, int zero, int one, int limit)

{

    if (pos == -1) {

        return zero >= one;

    }

    if (!limit && dp[pos][zero][one] != -1) {

        return dp[pos][zero][one];

    }

    int sum = 0, _o, _z, end = limit ? bit[pos] : 1;

    for (int i = 0; i <= end; ++i) {

        _o = one, _z = zero;

        if (i == 1) _o = one + 1;

        else if (i == 0 && one) _z = zero + 1;

        sum += dfs(pos-1, _z, _o, limit && i==end);

    }

    if (!limit) dp[pos][zero][one] = sum;

    return sum;

}



int Cal(int x)

{

    int idx = -1;

    while (x) {

        bit[++idx] = x % 2;

        x /= 2;

    }

    return dfs(idx, 0, 0, 1);

}



int main()

{

    memset(dp, 0xff, sizeof (dp));

    while (scanf("%d %d", &a, &b) == 2) {

        a -= 1;

        printf("%d
", Cal(b) - Cal(a));

    }

    return 0;    

}