Round Numbers POJ - 3252 | 数位dp

debug了一上午，还是做的少，应该想到先导0的影响的

题意：
问一个区间的数有多少个二进制中0的个数大于1
分析：
1、dp[i][j]表示第i位之前0与1个数差为j且该位valid != 0（也即无前导零）时，满足题意的数的总数。
2、由于差可能为负，所以整体+32
3、注意如果当前位有前导零，那么其计算的结果数不能放入dp数组（使得结果偏小）。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(a) cout << "debug :" << a << endl
#define fi first
#define se second
const int maxn = 1e6;
const int inf = 0x3f3f3f3f;
int dp[33][70];
int v[33];

int dfs(int pos, int valid, int dif, int limit)
{
    if(!pos) return dif >= 0;
    if(!limit && valid && ~dp[pos][dif + 32]) return dp[pos][dif + 32];
    int up = limit ? v[pos] : 1;
    ll res = 0;
    for(int i = 0; i <= up; i++)
    {
        res += dfs(pos - 1, valid || i, (valid || i) ? (!i ? dif + 1 : dif - 1) : 0, limit && i == up);
        //if(pos == 4) cout << res << endl;
    }
    if(!limit && valid) dp[pos][dif + 32] = res;
    return res;
}

int work(int x)
{
    int pos = 0;
    while(x)
    {
        v[++pos] = x & 1;
        x >>= 1;
    }
    return dfs(pos, 0, 0, 1);//一开始假设有前导零,valid = 0
}

int main()
{
    int l, r;
    mem(dp, -1);
    cin >> l >> r;
    cout << work(r) - work(l - 1) << endl;
}