hdu 5898 odd-even number 数位DP

思路：数位DP，套着数位DP的模板搞一发就可以了不过要注意前导0的处理，dp[pos][pre][status][ze]
pos:当前处理的位
pre:上一位的奇偶性
status：截止到上一位的连续段的奇偶性
ze:是否有前导0
/**************************************************************

    Problem:hdu 5898 odd-even number

    User: youmi

    Language: C++

    Result: Accepted

    Time:0MS

    Memory:1580K

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo 0x3fffffff

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

ll Pow(ll base, ll n, ll mo)

{

    ll res=;

    while(n)

    {

        if(n&)

            res=res*base%mo;

        n>>=;

        base=base*base%mo;

    }

    return res;

}

//***************************

int n;

const int maxn=+;

const ll mod=;

int digit[];

ll dp[][][][];

int tot=;

ll dfs(int pos,int pre,int status,int ze,int limit)

{

    if(pos<)

    {

        if(pre%==&&status%==)

            return ;

        else if(pre%==&&status%==)

            return ;

        else

            return ;

    }

    if(!limit&&dp[pos][pre][status][ze]!=-)

        return dp[pos][pre][status][ze];

    int ed=limit?digit[pos]:;

    ll res=;

    if(ze)

        res+=dfs(pos-,,,,limit&&(==ed));

    else

    {

        if(pre%==)

            res+=dfs(pos-,,status^,ze,limit&&(==ed));

        else if(pre%==&&status==)

            res+=dfs(pos-,,,ze,limit&&(==ed));

    }

    rep(i,,ed)

    {

        if(i%&&pre)

            res+=dfs(pos-,,status^,,limit&&(i==ed));

        else if(i%==&&!pre)

            res+=dfs(pos-,,status^,,limit&&(i==ed));

        else if(i%&&!pre&&(status==||ze))

            res+=dfs(pos-,,,,limit&&(i==ed));

        else if(i%==&&pre&&(status==||ze))

            res+=dfs(pos-,,,,limit&&(i==ed));

    }

    if(!limit)

        dp[pos][pre][status][ze]=res;

    return res;

}

void work(ll num)

{

    tot=;

    while(num)

    {

        digit[tot++]=num%;

        num/=;

    }

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    int T_T;

    scanf("%d",&T_T);

    for(int kase=;kase<=T_T;kase++)

    {

        printf("Case #%d: ",kase);

        ll num;

        sclld(num);

        work(num-);

        ones(dp);

        ll temp=dfs(tot-,,,,);

        sclld(num);

        work(num);

        ones(dp);

        ptlld(dfs(tot-,,,,)-temp);

    }

    return ;

}
秒客网

hdu 5898 odd-even number 数位DP

相关文章
