当前位置：首页 > news >正文

HDU 5898 数位DP

news 来源：原创 2024/4/27 6:49:34

题意: 求满足数位上连续的奇数为偶数个，连续的偶数为奇数个的数的个数。
思路: 典型的数位DP，dp[i][p][l]一维表示数位第i位，二维表示上一位的奇偶性，三维表示在第i位之前保持上一位的奇偶性的长度的奇偶性。

我的第一层传入的p和l为1,0。因为0个奇数是满足偶数个奇数的性质的，即数位上只有奇数个偶数的的数是满足条件的。

#include <iostream>
#include <string.h>
#include <cstdio>
#define LL long long
using namespace std;
int wei[30];
LL dp[30][2][2];	//后两维仅用来判断奇偶足够 
LL dfs(int pos, int limit, int lead, int p, int l)
{
	if(pos == -1)
	{
		if(lead) return 1;			
		//都是前导零即0满足，没这句也是可以的。如果前面所有的位都是前导零的话， 
		//传到pos=-1位p=1,l=0正好是满足偶数个奇数的性质的，其实0本身就是这性质 
		if(p && !(l&1)) return 1;	
		if(!p && (l&1)) return 1;
		return 0;
	}
	if(!lead && !limit && dp[pos][p][l&1] != -1) return dp[pos][p][l&1];
	int up = limit? wei[pos]: 9; LL res = 0;
	for(int i = 0; i <= up; ++i)
	{
		//pos位之前都是前导零，所以不会致使l增长，也会保持pos位前是偶数个奇数的特质
		if(lead && i==0)
		{ 
			res += dfs(pos-1, limit&&i==wei[pos], 1, 1, 0);
			continue;
		}
		//前面是奇数且i是奇数，所以直接可往后走 
		if(p && (i&1)) 
		res += dfs(pos-1, limit&&i==wei[pos], lead&&i==0, 1, l+1);
		
		//前面是奇数而i变为偶数，只有满足前面为偶数个奇数才能往后走 
		if(p && !(l&1) && !(i&1)) 
		res += dfs(pos-1, limit&&i==wei[pos], lead&&i==0, 0, 1);
		
		//前面是偶数且i是偶数，所以直接可往后走 
		if(!p && !(i&1)) 
		res += dfs(pos-1, limit&&i==wei[pos], lead&&i==0, 0, l+1);
		
		//前面是偶数而i变为奇数，只有满足前面为奇数个偶数才能往后走 
		if(!p && (l&1) && (i&1)) 
		res += dfs(pos-1, limit&&i==wei[pos], lead&&i==0, 1, 1);
		
	}
	if(!lead && !limit && dp[pos][p][l&1] == -1) dp[pos][p][l&1] = res;
	return res;
}
LL solve(LL k)
{
	if(k == 0) return 1;
	int cnt = 0;
	while(k)
	{
		wei[cnt++] = k%10;
		k /= 10;
	}
	return dfs(cnt-1, 1, 1, 1, 0);
}
int main()
{
	int t;
	LL l, r;
	memset(dp, -1, sizeof dp);
	scanf("%d", &t);
	for(int i = 1; i <= t; ++i)
	{
		scanf("%lld %lld", &l, &r);
		printf("Case #%d: %lld\n", i, solve(r)-solve(l-1));
	}
	return 0;
}

继续加油~