首页 > 代码库 > poj 3252 Round Numbers 数位dp

poj 3252 Round Numbers 数位dp

2024-09-21 05:39:16   216人阅读

题目链接：

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

题意：

求一段区间中二进制中0的数量要不能少于1的数量的数的个数。

思路：

套路  都是套路

http://blog.csdn.net/wust_zzwh/article/details/52100392

dp[pos][num],到当前数位pos,0的数量减去1的数量为num的方案数，一个简单的问题，中间某个pos位上num可能为负数(这不一定是非法的，因为我还没枚举完嘛，只要最终的num>=0才能判合法，中途某个pos就不一定了)，这里比较好处理，Hash嘛，最小就-32吧(好像),直接加上32，把32当0用。

显然我要统计0的数量，前导零是有影响的。dfs记忆化的时候要加一个变量lead代表这位是不是当前数的前导0

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 #define MS(a) memset(a,0,sizeof(a))
 7 #define MP make_pair
 8 #define PB push_back
 9 const int INF = 0x3f3f3f3f;
10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
11 inline ll read(){
12     ll x=0,f=1;char ch=getchar();
13     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
14     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
15     return x*f;
16 }
17 //////////////////////////////////////////////////////////////////////////
18 const int maxn = 1e5+10;
19 
20 int l,r,dp[50][maxn],a[50];
21 
22 int dfs(int pos,int sta,int lead,int limit){
23     if(pos == -1) return sta>=32;
24     if(!lead && !limit && dp[pos][sta]!=-1) return dp[pos][sta];
25 
26     int up = limit ? a[pos] : 1;
27     int re = 0;
28     for(int i=0; i<=up; i++){
29         if(lead && i==0)  re += dfs(pos-1,sta,lead,limit&&i==a[pos]);
30         else re += dfs(pos-1,sta+((i==0)?1:-1),lead&&i==0,limit&&i==a[pos]);
31     }
32     if(!lead && !limit) dp[pos][sta] = re;
33     return re;
34 }
35 
36 int solve(int x){
37     int pos = 0;
38     while(x){
39         a[pos++] = x%2;
40         x /= 2;
41     }
42     int re = dfs(pos-1,32,true,true);
43     return re;
44 }
45 
46 int main(){
47     memset(dp,-1,sizeof(dp));
48     cin >> l >> r;
49     int ans = solve(r) - solve(l-1);
50 
51     cout << ans << endl;
52 
53     return 0;
54 }

 

poj 3252 Round Numbers 数位dp


联系
我们