2016-09-22

HDU 5898 odd-even number【数位dp】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5898

题意：

给定$L,R$，求$L,R$之间有多少个数满足连续的奇数有偶数个，连续的偶数有奇数个。

分析：

数位dp，从高到低考虑每一位，dfs保存位置，该位置数的奇偶，是否满足条件，是否到达最大值，以及是否全为0。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 18 + 5;
typedef long long ll;
ll dp[maxn][2][2][2];
int a[maxn];
ll dfs(int pos, int kind, int ok, bool top, bool zero)
{
	if(pos < 0){
		if(zero) return 0;
		return ok;
	}
	if(!top && dp[pos][kind][ok][zero] != -1) return dp[pos][kind][ok][zero];
	ll ans = 0;
	int up = top?a[pos]:9;
	for(int i = 0; i <= up; i++){
	if(zero){
			if(i == 0) ans += dfs(pos - 1, 0, 0, top && i == up, 1);
			else ans += dfs(pos - 1, i & 1, (i & 1)?0:1, top && i == up, 0);
		}else if(!ok){
			if((i & 1) == kind) ans += dfs(pos - 1, kind, true, top && i == up, 0);
		}else{
			if((i & 1) == kind) ans += dfs(pos - 1, kind, false, top && i == up, 0);
			else ans += dfs(pos - 1, i & 1, (i & 1)?0:1, top && i == up, 0);
		}
	}	
	if(!top) dp[pos][kind][ok][zero] = ans;
	return ans;
}
ll solve(ll x)
{
	int len = 0;
	while(x){
		a[len++] = x % 10;
		x /= 10;
	}
	memset(dp, -1, sizeof(dp));
	return dfs(len - 1, 0, 1, 1, 1);
}
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; tt++){
		ll l, r;scanf("%lld%lld", &l, &r);	
		printf("Case #%d: %lld\n", tt, solve(r) - solve(l - 1));
	}
	return 0;
}