POJ 3252 Round Numbers（数位dp）-白红宇

POJ 3252 Round Numbers（数位dp）

阅读量：5084 次

发布时间：2019-06-13

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

题意：

求在区间内有多少个数转化成2进制后0的数量比1的数量多。

思路：

这道题目就要考虑前导0的影响了，如果前面是0的话，前导0的0不要去计数。注意好这点就可以了。

dp[pos][num0][num1][limit]表示分析到第pos位时，num0为0的个数，num1为1的个数。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             10 #include
              
               11 using namespace std;12 typedef long long ll;13 const int INF = 0x3f3f3f3f;14 const int maxn=100000+5;15 16 int l,r;17 int dp[50][50][50];18 int dig[50];19 20 int dfs(int pos, int num0, int num1, bool lead, bool limit)21 {22 if(pos==-1) return num0>=num1;23 if(!limit && dp[pos][num0][num1]!=-1) return dp[pos][num0][num1];24 int up=limit?dig[pos]:1;25 int ans=0;26 for(int i=0;i<=up;i++)27 {28 if(lead && i==0) ans+=dfs(pos-1,num0,num1,lead,limit&&i==dig[pos]);29 else ans+=dfs(pos-1,num0+(i==0),num1+(i==1),0,limit&&i==dig[pos]);30 }31 if(!limit) dp[pos][num0][num1]=ans;32 return ans;33 }34 35 int solve(int x)36 {37 int pos=0;38 while(x)39 {40 dig[pos++]=x&1;41 x>>=1;42 }43 return dfs(pos-1,0,0,1,1);44 }45 46 int main()47 {48 //freopen("in.txt","r",stdin);49 memset(dp,-1,sizeof(dp));50 scanf("%d%d",&l,&r);51 printf("%d\n",solve(r)-solve(l-1));52 return 0;53 }