1. 首页
2. 数位DP
3. 本页

HDU 5898 odd-even number (数位dp)

题目链接：点我~~

题意：一个数字，它每个数位上的奇数都形成偶数长度的段，偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数。

思路：裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的值的奇偶性和长度信息，还有是否前导零。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int MOD = 2520;
const int MAXN = 320000+10;

LL dp[22][3][22][3];
int dig[22];

LL dfs(int len,int jud,int siz,bool zero,bool mxl)
{
    if(!len)
    {
        if(jud && siz%2==0)
        {
            return 1;
        }
        else if(!jud && siz%2)
        {
            return 1;
        }
        else
            return 0;
    }
    if(!mxl && dp[len][jud][siz][zero]!=-1)
    {
        return dp[len][jud][siz][zero];
    }
    LL res=0;
    int maxlen=mxl?dig[len]:9;
    for(int i=0; i<=maxlen; ++i)
    {
        if(zero)
        {
            if(i==0)
                res+=dfs(len-1,0,0,1,mxl && (i==maxlen));
            else
            {
                if(i&1)
                    res+=dfs(len-1,1,1,0,mxl && (i==maxlen));
                else
                    res+=dfs(len-1,0,1,0,mxl && (i==maxlen));
            }
        }
        else
        {
            if(jud)
            {
                if(i&1)
                    res+=dfs(len-1,1,siz+1,0,mxl && (i==maxlen));
                else
                {
                    if(siz%2==0)
                        res+=dfs(len-1,0,1,0,mxl && (i==maxlen));
                }
            }
            else
            {
                if(i&1)
                {
                    if(siz%2)
                        res+=dfs(len-1,1,1,0,mxl && (i==maxlen));
                }
                else
                {
                    res+=dfs(len-1,0,siz+1,0,mxl && (i==maxlen));
                }
            }
        }

    }
    if(!mxl )
    {
        dp[len][jud][siz][zero]=res;
    }
    return res;
}

LL solve(LL x)
{
    memset(dig,0,sizeof(dig));
    int len=0;
    while(x)
    {
        dig[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,true,true);
}

int main()
{
    LL l,r;
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    int casee=1;
    while(t--)
    {
        cin>>l>>r;
        printf("Case #%d: ",casee++);
        cout<<(solve(r)-solve(l-1))<<endl;
    }

    return 0;
}