POJ3252 Round Numbers（数位DP）

本文主要是介绍POJ3252 Round Numbers（数位DP），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在二进制数上进行数位DP，在dp数组中就记录num0和num1，方便递归到边界时判断该数是否为round number，是则加1。

套用记忆化递归模板：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int dp[40][40][40];
 5 int dig[12];
 6 /*求一个区间内Round Numbers（二进制0的个数不小于1的个数）的个数。 
 7   状态dp[pos][num0][num1]；
 8   pos为当前数位，num0为二进制中0的个数，num1为二进制中1的个数； 
 9   lead表示前导零； 
10   limit表示数位限制。
11 */
12 
13 int dfs(int pos,int num0,int num1,bool lead,bool limit){//前导0，限制 
14     if(pos==0) return num0>=num1;
15     if(!limit&&!lead&&dp[pos][num0][num1]!=-1) return dp[pos][num0][num1];
16     int len=limit?dig[pos]:1;
17     int ans=0;
18     for(int i=0;i<=len;i++){
19         if(lead&&!i) ans+=dfs(pos-1,0,0,1,limit&&i==len);
20         else ans+=dfs(pos-1,num0+(i==0),num1+(i==1),0,limit&&i==len);
21     }
22     if(!limit&&!lead) dp[pos][num0][num1]=ans;
23     return ans;
24 }
25 
26 int solve(int x){
27     int pos=0;
28     while(x){
29         dig[++pos]=x%2;//转化为二进制处理每一位 
30         x/=2;
31     }
32     return dfs(pos,0,0,1,1);
33 }
34 
35 int main(){
36     int a,b;
37     memset(dp,-1,sizeof(dp));
38     while(~scanf("%d%d",&a,&b)){
39         memset(dp,-1,sizeof(dp));
40         printf("%d\n",solve(b)-solve(a-1));
41     }
42     return 0;
43 }

这篇关于POJ3252 Round Numbers（数位DP）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！