程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3252 Round Numbers（數位dp）

poj 3252 Round Numbers（數位dp）

編輯：C++入門知識

poj 3252 Round Numbers（數位dp）

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;
}