题目链接：http://poj.org/problem?id=3252
题目大意：给你两个数L，R，求[L, R]区间内，二进制下0的个数>1的个数的数字个数。

这里和之前的题不同的是：有前导0的影响。所以必须满足没有前导0和没有上界限制才能记忆化递归。

#include <bits/stdc++.h>

#define LL long long
using namespace std;
int a[35];
int dp[35][35][35];
int dfs(int pos, int s1, int s2, int Lead, int mt)//s1:0的个数， s2:1的个数 Lead：前导0 mt：限制
{
    if(pos==-1)
    {
        if(s1>=s2)//0的个数>1的个数
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    if(!mt&&!Lead&&dp[pos][s1][s2]!=-1)//必须满足两个条件
    {
        return dp[pos][s1][s2];
    }

    int Len=mt?a[pos]:1;
    int ans=0;
    for(int i=0;i<=Len;i++)
    {
        if(i==0)
        {
            if(Lead)
            {
                ans+=dfs(pos-1, s1, s2, Lead, mt&&i==a[pos]);//有前导0时,这位取0，s1, s2不变化
            }
            else
            {       
                ans+=dfs(pos-1, s1+1, s2, Lead, mt&&i==a[pos]);//没有前导0时,这位取0，s1+1
            }
        }
        else
        {
            ans+=dfs(pos-1, s1, s2+1, false, mt&&i==a[pos]);//取1时, s2+1
        }
    }

    if(!Lead&&!mt)
    {
        dp[pos][s1][s2]=ans;
    }

    return ans;

}

int slove(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%2;
        x/=2;
    }

    return dfs(pos-1, 0, 0, true, true);
}

int main()
{
    memset(dp, -1, sizeof(dp));
    int L, R;
    scanf("%d%d",&L,&R);
    printf("%d\n", slove(R)-slove(L-1));

    return 0;
}