POJ 3252 (数位DP)

###POJ 3252 题目链接 ###

题目大意:给你一段区间 [Start,Finish] ,在这段区间中有多少个数的二进制表示下,0 的个数 大于等于 1 的个数。


分析:

1、很显然是数位DP,枚举这区间中所有数的二进制位数。由于与 0 的个数有关,故需要用 lead 标记前导零情况。

2、然后就是要处理 1 的个数与 0 的个数,故 dp 的第二维状态即要表示出枚举到当前位 pos 时所拥有的 0 的个数 (或 1)。

但是你会发现,如果当前知道的是 前面几位中 0 的个数,为了满足题意,我还需要知道前面几位中 1 的个数,然后求差值,再到后面 pos 位中找相应的 dp 值。故为了简便,第二维设的应该是当前 1~pos位中,1的个数减去 0 的个数的差值。由于差值可能为负数,且 20亿 最高不会超过 32 位(二进制),故取 32 为中间值,然后根据枚举位上的 1 或 0 来加减。

故 dp[i][j] 表示,在 1~ i 位中,1 与 0 的个数差值为 j (与 32 的差值)。

本题的记忆化搜索: 当从最高位枚举到第 pos 位时,第 1 ~ pos 位上与当前状态对应于 dp[pos][差值] 时满足条件的个数,这个差值来源于 最高位到 pos 位 。比如从最高位的前三位都为 1 ,那么此时从最高位枚举了 3 位,且sum = 32 + 3 = 35 ,那么 dp[pos][sum] 即求在 sum 为 35 的情况下,第 1 ~ pos 位上,能使得最后 sum<=32 的状态个数。

代码如下:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[][],a[];
int N,M,res;
int dfs(int pos,int sum,bool lead,bool limit){
if(pos==) return sum<=;
if(!limit&&!lead&&dp[pos][sum]!=-) return dp[pos][sum];
int up=limit?a[pos]:;
int ans=;
for(int i=;i<=up;i++){
if(lead&&i==) ans+=dfs(pos-,sum,lead,limit&&i==a[pos]);
else ans+=dfs(pos-,sum+(i==?-:),false,limit&&i==a[pos]);
}
if(!limit&&!lead) dp[pos][sum]=ans;
return ans;
}
int solve(int x)
{
int pos=;
while(x){
a[++pos]=(x&);
x>>=;
}
res=pos;
return dfs(pos,,true,true);
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
memset(dp,-,sizeof(dp));
while(~scanf("%d%d",&N,&M)){
printf("%d\n",solve(M)-solve(N-) );
}
}
上一篇:R语言数据的输入


下一篇:Android 手机摇一摇功能的实现