POJ3252Round Numbers(数位dp)-白红宇

POJ3252Round Numbers(数位dp)

阅读量：6473 次

发布时间：2019-06-23

本文共 1066 字，大约阅读时间需要 3 分钟。

题意

给出区间$[A, B]$，求出区间内的数转成二进制后$0$比$1$多的数的个数

$1 \leqslant A, B \leqslant 2,000,000,000$

Sol

比较zz的数位dp

直接在二进制下dp就好

$f[i][ze][on]$表示第$i$位，填了$ze$个$0$，$on$个1的方案数

#include
     
      #include
      
       #include
       
        // #include
        using namespace std;#define LL long longconst LL MAXN = 101;LL A, B;LL num[MAXN], tot, f[MAXN][MAXN][MAXN];LL dfs(LL x, bool lim, LL ze, LL on) {    if(x == 0) return         (ze != -1) && (on != -1) && (ze >= on);    if(!lim && f[x][ze][on]) return f[x][ze][on];    LL ans = 0;    for(LL i = 0; i <= (lim ? num[x] : 1); i++) {        if(i == 0) ans += dfs(x - 1, lim && (i == num[x]), ze == -1 ? 1 : ze + 1, on);        else {            if(on == -1) ans += dfs(x - 1, lim && (i == num[x]), 0, 1);            else ans += dfs(x - 1, lim && (i == num[x]), ze, on + 1);        }    }    if(!lim) f[x][ze][on] = ans;    return ans;}LL solve(LL x) {    tot = 0;    while(x) num[++tot] = x % 2, x >>= 1;    return dfs(tot, 1, -1, -1);}int main() {    cin >> A >> B;    cout << solve(B) - solve(A - 1);    return 0;}/*1234 44442*/