HDU 5898 odd-even number——数位dp

HDU 5898 odd-even number——数位dp

题意：求一个区间内满足下面条件的数的个数：

数位中连续的奇数个数为偶数，连续的偶数个数为奇数。

思路：考虑前导0的数位dp

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 20;int a[20];ll dp[20][20][2];ll rec(int pos, int state, int pre, bool limit, bool lead) { if (pos == -1) return (state & 1) != (pre & 1); if (!limit && !lead && dp[pos][state][pre] != -1) return dp[pos][state][pre]; int up = limit ? a[pos] : 9; ll ans = 0; for (int i = 0; i <= up; i++) { if (lead) { if (i == 0) ans += rec(pos - 1, 0, 0, limit && i == a[pos], true); else ans += rec(pos - 1, 1, i & 1, limit && i == a[pos], false); } else { if (i & 1) { if (pre & 1) ans += rec(pos - 1, state + 1, i & 1, limit && i == a[pos], false); else if (!(pre & 1) && (state & 1)) ans += rec(pos - 1, 1, i & 1, limit && i == a[pos], false); } else { if (!(pre & 1)) ans += rec(pos - 1, state + 1, i & 1, limit && i == a[pos], false); else if (pre & 1 && !(state & 1)) ans += rec(pos - 1, 1, i & 1, limit && i == a[pos], false); } } } if (!limit && !lead) dp[pos][state][pre] = ans; return ans;}ll solve(ll x) { int pos = 0; while (x) { a[pos++] = x % 10; x /= 10; } return rec(pos - 1, 0, 0, true, true);}int main(){ int T; scanf("%d", &T); ll L, R, flag = 0; while (T--) { scanf("%lld %lld", &L, &R); memset(dp, -1, sizeof(dp)); printf("Case #%lld: %lld\n", ++flag, solve(R) - solve(L - 1)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。