题目链接：[kuangbin带你飞]专题十五 数位DP E - Round Numbers

题意

给定区间。求转化为二进制后当中0比1多或相等的数字的个数。

思路

将数字转化为二进制进行数位dp，由于一个二进制数的最高位必须为1。所以设置变量first记录前面位是否有1，若有1，则可随意放，否则，仅仅可放1。

同一时候。上面的推断决定了搜索时len的大小与二进制本身的长度不一定相等，所以需两个变量对1和0的个数进行记录。

用dp[a][b][c]保存长度a，b个0，c个1的数字个数。记忆化搜索。

代码

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <vector>

using namespace std;

#define LL long long

int dp[33][33][33];

int dis[33];

int dfs(int len, int cnt0, int cnt1, bool first, bool flag)

{

    if(len < 0)

        return (first || cnt0>cnt1);

    if(!flag && !first && dp[len][cnt0][cnt1]!=-1)

        return dp[len][cnt0][cnt1];

    int end = flag?dis[len]:1;

    int ans = 0;

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

    {

        if(first)

        {

            if(i)

                ans += dfs(len-1, 0, 0, 0, flag&&i==end);

            else

                ans += dfs(len-1, 0, 0, 1, flag&&i==end);

        }

        else

        {

            if(i)

                ans += dfs(len-1, cnt0, cnt1+1, 0, flag&&i==end);

            else

                ans += dfs(len-1, cnt0+1, cnt1, 0, flag&&i==end);

        }

    }

    if(!flag && !first)

        dp[len][cnt0][cnt1] = ans;

    return ans;

}

int solve(int n)

{

    int len = 0;

    while(n)

    {

        dis[len++] = n&1;

        n >>= 1;

    }

    return dfs(len-1, 0, 0, 1, 1);

}

int main()

{

    int l, r;

    memset(dp, -1, sizeof(dp));

    while(cin>>l>>r)

        cout<<solve(r)-solve(l-1)<<endl;

    return 0;

}