hdu5898-odd-even number-2016沈阳网络赛-数位dp

题目链接

题意：一个数，如果他所有的连续奇数数字段的长度为偶数，所有的连续偶数数字段的长度为奇数，那么就称这个数为odd-even number。现给你一个范围【L,R】,让你求出所有在L,R之间的odd-even number的个数

思路：orz，沈阳网络赛的签到题是这题……感觉要是我自己打这场，签到都签不了呀……比赛的时候还成功带着wtw菊苣在错误的路上越走越远……导致wtw菊苣4小时才a掉这题……还是太水了，完全不会数位dp……
其实这题很裸，pos表示到了第几位，pre表示前面一个的奇偶性，len表示当前段长度，inf表示上界，zero表示是否前导全是零（这题要注意0不能简单地算成偶数），记忆化搜索就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long dp[30][3][30][3];
int dig[30];
long long dfs(int pos,int pre,int len,int inf ,int zero) 
{
	if(pos==0)
	{   int ll=len%2;
		if(pre+ll==1)return 1;
		 else return 0;
	}
	long long ans=0;
	if(!inf && dp[pos][pre][len][zero]!=0)return dp[pos][pre][len][zero];
	int end=inf?dig[pos]:9;
	if(zero)//前全0 
	{
		for(int i=0;i<=end;i++)
		{
			if(i==0)ans+=dfs(pos-1,0,0,inf && end==i,1);
			 else
			 if(i%2==1)
			 {
			 	ans+=dfs(pos-1,1,1,inf && end==i,0); 
			 }
			 else
			 if(i%2==0)
			 {
			 	ans+=dfs(pos-1,0,1,inf && end==i,0);
			 }
			   
		}
	}
	else
	for(int i=0;i<=end;i++)   
	{
		 if(i%2==1)    //当前填奇数，且非前全0 
	      {
	      	if(pre==1)ans+=dfs(pos-1,1,len+1,inf && end==i,0);
	      	if(pre==0 && len%2==1)ans+=dfs(pos-1,1,1,inf && end==i,0);
		  }
		  else
		  if(i%2==0)   //当前填偶数，且非前全0  
		  {
		  	if(pre==0)ans+=dfs(pos-1,0,len+1,inf && end==i,0);
		  	if(pre==1 && len%2==0)ans+=dfs(pos-1,0,1,inf && end==i,0);
		  }
	}
	if(!inf)dp[pos][pre][len][zero]=ans;
	return ans;
}
int main()
{
	int i,j,k,m,n;
	long long l,r;
	int t;
	scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
	{   memset(dig,0,sizeof(dig));
		scanf("%lld%lld",&l,&r);
	    int pos=0;
	    l--;
		while(l>0)
		{
		  dig[++pos]=l%10;
		  l=l/10;	
		}
		memset(dp,0,sizeof(dp));
	    long long ans1=dfs(pos,0,0,1,1);
		//printf("L:%lld\n",ans1);
		pos=0;
		memset(dig,0,sizeof(dig));
		while(r>0)
		{
			dig[++pos]=r%10;
			r/=10;
		}
		memset(dp,0,sizeof(dp));
		long long ans2=dfs(pos,0,0,1,1);
		//printf("R:%lld\n",ans2);
		printf("Case #%d: %lld\n",kase,ans2-ans1);		
	}
	return 0;    
}