POJ 3252 Round Numbers（数位dp）

题意：

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

思路：

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

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

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
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
",solve(r)-solve(l-1));
52     return 0;
53 }