【數位DP(前導零的處理)】POJ 3252 Round Numbers

POJ 3252 Round Numbers

題意：

• 求區間中二進制表示0的個數不小于1的個數的數的個數

思路：

• 這個必須要考慮前導零的影響，是以設定一個布爾變量，用來記錄目前位的高位是不是都是0。
• 然後的話cnt初始值設為32（int最大數位為32位），如果高位有1，且目前位為0，那麼cnt + 1；目前位為1，那麼cnt - 1。跑完所有的數位之後，如果cnt >= 32就說明0的個數不小于1.
• 記憶化的時候就必須高位有1并且無限制才可以更新dp

！！dp二維要開一維的兩倍，因為我們的基點設定的是32，上下浮動有32，是以要開夠。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <limits>
#include <set>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxN = 5e3;
int dp[35][70];
int a[35];
int s, e;

int dfs(int pos, int cnt, bool lead, bool limit)
{
    if(pos == -1)
        return cnt >= 32;
    if(!limit && !lead && dp[pos][cnt] != -1)
        return dp[pos][cnt];
    int up = limit ? a[pos] : 1;
    int ans = 0;
    for(int i = 0; i <= up; i ++ )
    {
        if(lead && i == 0)
            ans += dfs(pos - 1, cnt, lead, limit && i == a[pos]);
        else
            ans += dfs(pos - 1, cnt + (i == 0 ? 1 : -1), lead && i == 0, limit && i == a[pos]);
    }
    if(!limit && !lead)
        dp[pos][cnt] = ans;
    return ans;
}

int solve(int x)
{
    int pos = 0;
    while(x)
    {
        a[pos ++ ] = x & 1;
        x >>= 1;
    }
    return dfs(pos - 1, 32, true, true);
}
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &s, &e);
    printf("%d\n", solve(e) - solve(s - 1));
    return 0;
}