[原创]HDU 5898&&2016 ACM/ICPC Asia Regional Shenyang Online/ odd-even number [数位DP]【动态规划】

# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define lalal puts("*******");
/*************************************/

int num[30],len;
LL dp[30][3][30][3];
//weishu jiou changdu zhuangtai
LL dfs(int pos,int pre,int x,int limit,int status,int lengh)
{
    if(pos<0)  return status&&(lengh+x)%2==1;

    if(dp[pos][x][lengh][status]!=-1&&!limit)
        return dp[pos][x][lengh][status];

    int endi=9;
    if(limit) endi = num[pos];

    LL res = 0;
    for(int i=0; i<=endi; i++)
    {
        if(pre==0&&i==0)//qiandao00
        {
            res+=dfs(pos-1,0,0,0,1,0);
        }
        else
        {
            if(pre==0)
            {
                res+=dfs(pos-1,1,i%2,limit&&(i==endi),1,1);

            }
            else
            {
                res+=dfs(pos-1,1,i%2,limit&&(i==endi),(i%2==x)?status:((lengh+x)%2==1)&&status,(i%2==x)?(lengh+1):(1));

            }
        }
    }
    if(!limit) dp[pos][x][lengh][status] =  res;
    return  res;
}
LL solve(LL n)
{
    if(n<=0) return 0;

    len = 0;
    while(n)
    {
        num[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,0,0,1,1,0);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int _,p;
    scanf("%d",&_);

    p=0;
    while(_--)
    {
        LL l,r;
        scanf("%I64d%I64d",&l,&r);
        printf("Case #%d: %I64d\n",++p,solve(r)-solve(l-1));
    }

    return 0;
}