poj 3252 Round Numbers（数位dp） - c++编程基础

TOP

poj 3252 Round Numbers（数位dp）

2015-07-20 17:48:16 来源: 作者: 【大中小】浏览:1次

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

"Round Number "被称为其二进制形式中0的个数比1的个数多。求[x,y]区间内“Round Number”的个数。

计数的时候最重要的是处理前导零，前导零不算数，因此与SCOI2009一样，增加一个标记变量first，标志着当前这意味是不是首位，不是首位的话1和0的个数都为0，否则根据枚举的1或0进行记忆化搜索。

起初设的dp[i][j]表示到第i位之前0和1个数的差值，但这样不好存储吗，下标有可能为负值。可以设dp[i][j][k]表示第i位之前0和1的个数分别为j和k。

#include 
  
   
#include 
   
     #include 
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; int dig[50]; int dp[50][50][50]; //dp[i][j][k]表示到i为0的个数为j，1的个数为k int dfs(int len, int first, int num0, int num1, int up) { if(len == 0) { if(num0 >= num1) return 1; return 0; } if(!up && !first && dp[len][num0][num1] != -1) return dp[len][num0][num1]; int n = up ? dig[len] : 1; int res = 0; for(int i = 0; i <= n; i++) { if(first)//当前是首位 { if(i == 0) //同时i取0那么下一位是首位，到i位为止0和1的个数都是0 res += dfs(len-1,1,0,0,up&&i==n); else res += dfs(len-1,0,num0,num1+1,up&&i==n);//这一位是首位，1的个数加1 } else //不是首位的话，对0或1加的个数1 { if(i == 0) res += dfs(len-1,0,num0+1,num1,up&&i==n); else res += dfs(len-1,0,num0,num1+1,up&&i==n); } } if(!up && !first) dp[len][num0][num1] = res; return res; } int cal(int num) { int len = 0; while(num) { dig[++len] = num % 2; num /= 2; } return dfs(len,1,0,0,1); } int main() { int x,y; memset(dp,-1,sizeof(dp)); while(~scanf("%d %d",&x,&y)) { printf("%d\n",cal(y) - cal(x-1) ); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++技术问题总结-第7篇 map、vect..	下一篇：HDU4746 Mophues(莫比乌斯反演)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: