首页 > 代码库 > hdu 5898 odd-even number(数位dp）
hdu 5898 odd-even number(数位dp）
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.
题意：一个数中所有连续的奇数长度都为偶数，所有连续偶数的长度都为奇数。我们要找一个区间内一共有多少个这样的数。
区间范围（1～9*10^18)所以显然是数位dp搞。设dp[len][count][temp]，temp=1表示偶数，temp=2表示奇数，temp=0表示取首位0时，
count表示到len位置有几个奇数或偶数个。显然简单的搜索，标准数位dp
#include <iostream>#include <cstring>using namespace std;typedef long long ll;ll dp[22][22][3];int dig[20];ll dfs(int len , int count , int temp , int flag , int first) { if(len == 0) { if(temp == 1) { if(count % 2 != 0) { return 1; } else { return 0; } } if(temp == 2) { if(count % 2 == 0) { return 1; } else { return 0; } } return 0; } if(!flag && !first && dp[len][count][temp] != -1) { return dp[len][count][temp]; } int n = flag ? dig[len] : 9; ll sum = 0; for(int i = 0 ; i <= n ; i++) { if(first) { if(i == 0) { sum += dfs(len - 1 , 0 , 0 , flag && i == n , first && i == 0); } else { if(i % 2 == 0) { sum += dfs(len - 1 , count + 1 , 1 , flag && i == n , first && i == 0); } else { sum += dfs(len - 1 , count + 1 , 2 , flag && i == n , first && i == 0); } } } else { if(i % 2 == 0) { if(temp == 1) { sum += dfs(len - 1 , count + 1 , 1 , flag && i == n , first && i == 0); } if(temp == 2) { if(count % 2 == 0) { sum += dfs(len - 1 , 1 , 1 , flag && i == n , first && i == 0); } } } else { if(temp == 1) { if(count % 2 != 0) { sum += dfs(len - 1 , 1 , 2 , flag && i == n , first && i == 0); } } if(temp == 2) { sum += dfs(len - 1 , count + 1 , 2 , flag && i == n , first && i == 0); } } } } if(!flag && !first) { dp[len][count][temp] = sum; } return sum;}ll Get(ll x) { int len = 0; memset(dp , -1 , sizeof(dp)); memset(dig , 0 , sizeof(dig)); if(x == 0) len = 1; while(x) { dig[++len] = x % 10; x /= 10; } return dfs(len , 0 , 0 , 1 , 1);}int main(){ int t; cin >> t; int ans = 0; while(t--) { ans++; ll l , r , gg; cin >> l >> r; cout << "Case #" << ans << ": " << Get(r) - Get(l - 1) << endl; } return 0;}hdu 5898 odd-even number(数位dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。