首页 > 代码库 > HDU 5898 odd-even number 数位DP
HDU 5898 odd-even number 数位DP
odd-even number
Problem Description
For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).
Input
First line a t,then t cases.every line contains two integers L and R.
Output
Print the output for each case on one line in the format as shown below.
Sample Input
2 1 100 110 220
Sample Output
Case #1: 29Case #2: 36
基础的数位DP
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 600+10, M = 1e2+11, mod = 1e9+7, inf = 0x3fffffff;LL L,R,dp[80][2][80][2],vis[80][2][80][2];int d[80];long long dfs(int dep,int f,int p,int x) { if(dep < 0) return (p%2!=x%2); if(f && vis[dep][f][p][x]) return dp[dep][f][p][x]; if(f) { long long& ret = dp[dep][f][p][x]; vis[dep][f][p][x] = 1; for(int i=0;i<=9;++i) { if(x == -1) { if(i == 0) ret += dfs(dep-1,f,1,-1); else ret += dfs(dep-1,f,1,i%2); } else { if(i%2 == x) { ret += dfs(dep-1,f,p+1,i%2); }else { if(p%2 == x) continue; ret += dfs(dep-1,f,1,i%2); } } } return ret; } else { LL ret = 0; for(int i=0;i<=d[dep];++i) { if(x == -1) { if(i == 0) ret += dfs(dep-1,i<d[dep],1,-1); else ret += dfs(dep-1,i<d[dep],1,i%2); } else { if(i%2 == x) { ret += dfs(dep-1,i<d[dep],p+1,i%2); }else { if(p%2 == x) continue; ret += dfs(dep-1,i<d[dep],1,i%2); } } } return ret; }}long long solve(long long x){ memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); int len = 0; while(x){ d[len++] = x%10; x/=10; } return dfs(len-1,0,0,-1);}int main() { int T,cas = 1; scanf("%d",&T); while(T--) { scanf("%I64d%I64d",&L,&R); printf("Case #%d: %I64d\n",cas++,solve(R) - solve(L-1)); } return 0;}
HDU 5898 odd-even number 数位DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。