poj 3252 数位dp

题意:一个二进制的数，如果0的个数大于1的个数，那么我们称这个数为Round Numbers，求给定区间（十进制表示）中Round Numbers的个数

题解：数位dp,不过这里枚举的时候lead标记就有作用了（前导零，也是为了防止状态的冲突）

ac代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dp[50][70];
int a[70];
int dfs(int pos,int num,bool lead,bool limit)// num 0比1多的个数
{
    if(pos==-1) return num>=32;// hash一下 数组的index不能为负数
    if(!lead && !limit && dp[pos][num]!=-1) return dp[pos][num];
    // 可以有一步减枝
    int up=limit ? a[pos]:1;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        if(i==1) ans+=dfs(pos-1,num-1,lead && i==0,limit && i==a[pos]);
        else
        {
            if(lead) ans+=dfs(pos-1,num,lead,limit && i==a[pos]);
            else ans+=dfs(pos-1,num+1,lead && i==0,limit && i==a[pos]);
        }
    }
    if( !lead && !limit) dp[pos][num]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%2;
        x/=2;
    }
    return dfs(pos-1,32,true,true);
}
int main()
{
    int x,y;
    memset(dp,-1,sizeof(dp));
    while(cin>>x>>y)
    {
        cout<<solve(y)-solve(x-1)<<endl;
    }
    return 0;
}

Limit 以及 lead 两个参数都是为了花费较小的代码来使状态不冲突的方式