欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

POJ3252Round Numbers(数位dp)

程序员文章站 2022-07-12 07:56:03
题意 给出区间$[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$个 ......

题意

给出区间$[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<cstdio>
#include<cstring>
#include<iostream>
// #include<map>
using namespace std;
#define ll long long
const 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 4444
2
*/