HDU 5898：odd-even number 数位DP

odd-even number 

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5898

题意：

求区间内满足以下条件的数的个数

①每一位连续的奇数出现偶数次

②每一位连续的偶数出现奇数次 

 

题解：

区间DP水题，记0为出现奇数偶数次，1为出现奇数奇数次

记0为没有出现过偶数，1为出现偶数偶数次，2为出现偶数奇数次。

 

代码

#include<stdio.h>
#include<string.h>
#define Type long long
const int N=31;
Type dp[N][10][2][3][2]; int bit[N]; long long sum; bool change(bool status,int i,int pre,int sum1,int sum2) { if(pre==-1||!sum)return true; if(pre%2!=i%2) { if(i%2)return !(sum2%2); else return !(sum1%2); } else return true; } int Sum1(int i,int pre,int sum1,int sum2) { if(!sum||i%2!=pre%2)return i%2; return i%2?(sum1+1)%2:sum1; } int Sum2(int i,int pre,int sum1,int sum2) { if(!sum&&!i)return 0; if(!sum||i%2!=pre%2)return (i%2)?0:2; if(i%2)return sum2; else { if(!sum2)return 2; else return sum2==2?1:2; } }
Type dfs(int pos,int pre,bool limit,bool status,int sum1,int sum2) {
    sum=pre==-1?0:sum*10+pre; if(pos<1)return (status&&!(sum1%2)&&!(sum2%2))?1:0; if(!limit&&pre!=-1&&dp[pos][pre][sum1][sum2][status]!=-1) return dp[pos][pre][sum1][sum2][status]; int end=limit?bit[pos]:9;
    Type res=0; for(int i=0;i<=end;++i)
    res+=dfs(pos-1,i,limit&&(i==end),status&&change(status,i,pre,sum1,sum2),Sum1(i,pre,sum1,sum2),Sum2(i,pre,sum1,sum2)); if(!limit)dp[pos][pre][sum1][sum2][status]=res; if(pre!=-1)sum=(sum-pre)/10; return res; }
Type Get_Ans(Type x) {
    sum=0; int len=0; while(x||!len) {
        bit[++len]=x%10;
        x/=10; } return dfs(len,-1,true,true,0,0); } void solve() {
    Type l,r; int T,w=0;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T); while(T--) {
        scanf("%lld%lld",&l,&r);
        printf("Case #%d: %lld\n",++w,Get_Ans(r)-Get_Ans(l-1)); } } int main() {
    solve(); return 0; }