1. 首页
2. 数位DP
3. 本页

POJ 3252 Round Numbers (数位DP)

判断范围内二进制0比1多的数的个数~~

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int MOD = 2520;
const int MAXN = 320000+10;

LL dp[50][55][55];
int dig[50];

//因为不考虑前导0  所以需要多加一个状态来判断
LL dfs(int len,int sum0,int sum1,bool state,bool mxl)
{
    if(!len)
    {
        if(state)  //到最后还没放下 只能是0
        {
            return 1;
        }
        if(sum0>=sum1)
        {
            return 1;
        }
        return 0;
    }
    if(!mxl && !state && dp[len][sum0][sum1]!=-1)
    {
        return dp[len][sum0][sum1];
    }
    LL res=0;
    int maxlen=mxl?dig[len]:1;
    for(int i=0; i<=maxlen; ++i)
    {
        if(state)
        {
            if(i==0)
            {
                res+=dfs(len-1,0,0,1,mxl&& i==maxlen);
            }
            else
            {
                res+=dfs(len-1,sum0,sum1+1,0,mxl&& i==maxlen);
            }
        }
        else
        {
            if(i==0)
            {
                res+=dfs(len-1,sum0+1,sum1,0,mxl&& i==maxlen);
            }
            else
            {
                res+=dfs(len-1,sum0,sum1+1,0,mxl&& i==maxlen);
            }
        }
    }
    if(!mxl && !state)
    {
        dp[len][sum0][sum1]=res;
    }
    return res;
}

LL solve(LL x)
{
    memset(dig,0,sizeof(dig));
    int len=0;
    while(x)
    {
        dig[++len]=x&1;
        x>>=1;
    }
    return dfs(len,0,0,true,true);
}

int main()
{
    LL l,r;
    memset(dp,-1,sizeof(dp));
    while(cin>>l>>r)
    {
        cout<<(solve(r)-solve(l-1))<<endl;
    }

    return 0;
}

/*
1 2000000000

*/