hdu_5898_odd-even number(数位DP)

题意：

给你一个区间，问你这个区间中满足连续的偶数的位数为奇数，连续的奇数的位数是偶数的个数

题解：

设dp[i][j][k][l]为考虑当前第i位，上一位的奇偶性为j，已经连续了k位，是否有前导零

然后记忆化搜就行了

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 int dig[20],len;
 7 ll dp[20][2][20][2];
 8 
 9 ll dfs(int pos,int pre=0,int ln=0,bool inf=1,bool ze=1)//pre 1为奇，0为偶
10 {
11     if(!pos)
12     {
13         if(pre)return (ln&1)==0;
14         else return ln&1;
15     }
16     if(!inf&&dp[pos][pre][ln][ze]!=-1)return dp[pos][pre][ln][ze];
17     int en=inf?dig[pos]:9;ll ans=0;
18     F(i,0,en)
19     {
20         if(i&1)
21         {
22             if(ze)
23             {
24                 if(i==0)ans+=dfs(pos-1,0,0,inf&&i==en,1);
25                 else ans+=dfs(pos-1,1,1,inf&&i==en,0);
26             }
27             else if(pre==0)
28             {
29                 if(ln&1)ans+=dfs(pos-1,1,1,inf&&i==en,ze);
30             }else if(pre==1)
31             {
32                 ans+=dfs(pos-1,1,ln+1,inf&&i==en,ze);
33             }
34         }else
35         {
36             if(ze)
37             {
38                 if(i==0)ans+=dfs(pos-1,0,0,inf&&i==en,1);
39                 else ans+=dfs(pos-1,0,1,inf&&i==en,0);
40             }
41             else if(pre==0)ans+=dfs(pos-1,0,ln+1,inf&&i==en,ze);
42             else if(pre==1)
43             {
44                 if((ln&1)==0)ans+=dfs(pos-1,0,1,inf&&i==en,ze);
45             }
46         }
47     }
48     if(!inf)dp[pos][pre][ln][ze]=ans;
49     return ans;
50 }
51 
52 int main(){
53     int t,ic=1;ll l,r;
54     scanf("%d",&t);
55     while(t--)
56     {
57         memset(dp,-1,sizeof(dp));
58         scanf("%lld%lld",&l,&r),l--;
59         for(len=0;l;l/=10)dig[++len]=l%10;
60         ll tp=dfs(len);
61         for(len=0;r;r/=10)dig[++len]=r%10;
62         printf("Case #%d: %lld
",ic++,dfs(len)-tp);
63     }
64     return 0;
65 }

View Code