首页 > 代码库 > hdu_5898_odd-even number(数位DP)

hdu_5898_odd-even number(数位DP)

2024-08-13 20:26:29   219人阅读

题目链接：hdu_5898_odd-even number

题意：

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

题解：

设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         }else35         {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\n",ic++,dfs(len)-tp);63     }64     return 0;65 }
View Code

 

hdu_5898_odd-even number(数位DP)


联系
我们