程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LightOJ 1032 - Fast Bit Calculations (數位dp)

LightOJ 1032 - Fast Bit Calculations (數位dp)

編輯：C++入門知識

LightOJ 1032 - Fast Bit Calculations (數位dp)

問0~N內所有數的二進制形式中出現的連續的'11'的個數的和。

與LightOJ 1140類似，都是對一個數內一些特征的數目計數，像一個數中'11'或'0'的個數和。

設dp[i][j]表示處理到第i位時'11'出現的次數。

NC的錯誤，數組開小了，還一直覺得是十進制。。。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL __int64
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;

int dig[40];
LL dp[40][3][40]; //dp[i][j]表示到第i位有j個(1,1)對

LL dfs(int len, int pre, int sta,int up,int first)
{
	if(len == 0)
	{
		if(first)
			return 0;
		return (LL)sta;
	}
	if(!up && !first && dp[len][pre][sta] != -1)
		return dp[len][pre][sta];
	int n = up ? dig[len] : 1;
	LL res = 0;
	for(int i = 0; i <= n; i++)
	{
		if(first)
			res += dfs(len-1,i,0,up&&i==n,first&&i==0);
		else
		{
			if(i == 1 && pre == 1)
				res += dfs(len-1,i,sta+1,up&&i==n,first&&i==0);
			else
				res += dfs(len-1,i,sta,up&&i==n,first&&i==0);
		}
	}
	if(!up && !first)
		dp[len][pre][sta] = res;
	return res;
}

LL cal(int num)
{
	int len = 0;
	while(num)
	{
		dig[++len] = num % 2;
		num /= 2;
	}
	return dfs(len,0,0,1,1);
}

int main()
{
	int num;
	int test;
	scanf(%d,&test);

	for(int item = 1; item <= test; item++)
	{
		memset(dp,-1,sizeof(dp));
		scanf(%d,&num);
		printf(Case %d: %lld
,item,cal(num));
	}
	return 0;
}