Round Numbers（数位dp）-蒲公英云

Round Numbers（数位dp）

墨蓝 2022-02-19 03:39 359阅读 0赞

题目链接：

http://poj.org/problem?id=3252

分析：

本题我一开始思路便存在一定问题。
其实我们可以把每个数直接化成二进制保存在一个数组里面。通过改变数组里面0或者1的值便可以得到n以内的所有的数。然后，还需要注意一点，就是前导0的存在。前导0 是不计入最后的比较环节的。这是一点要注意的。
参考博客：https://blog.csdn.net/jk211766/article/details/81474632

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
#define scanll(a,b) scanf("%lld%lld",&a,&b);
typedef long long ll;
ll dp[110][100];
ll digit[20];
/*int check(ll num)
{错误代码思路
    int cnt1=0;
    int cnt0=0;
    if(num == 0) return 0;
    while(num)
    {
        if(num%2==0) cnt0++;
        else cnt1++;
        num=num/2;
    }
    return cnt0 >= cnt1;
}*/
int dfs(int pos, ll cnt0,int lead,int limit)
{
    if(-1 == pos) return cnt0>=32;
    //每次记忆化时，也要判断前导0 如果存在前导0 是不可以直接返回的。 
    if(!limit && !lead &&dp[pos][cnt0] != -1) return dp[pos][cnt0];
    ll cnt = 0;
    ll up = limit ? digit[pos] : 1;
    for(int i = 0; i <= up; i ++)
    {
        if(lead && i == 0)
            cnt += dfs(pos - 1,cnt0,lead,limit && i == digit[pos]);
        else
            cnt += dfs(pos - 1,cnt0 + (i == 0 ? 1 : -1),lead && i ==0,limit && i == digit[pos]);
    }
    //同理，存在前导0 不可以直接记录
    if(!limit && !lead ) dp[pos][cnt0] = cnt;
    return cnt;
}
int solve(ll num)
{
    int k=0;
    while(num)//化为二进制保存
    {
        digit[k++] = num % 2;
        num = num / 2;
    }
    return dfs(k - 1,32,1,1);
}
int main()
{
    ll n,m;
    scanll(n,m);
    memset(dp, -1 ,sizeof(dp));
    if(m == 1)
        printf("%lld\n",solve(m));
    else
    printf("%lld\n",(ll)solve(m) - solve(n-1));
}