POJ 3252 Round Numbers——数位dp

POJ 3252 Round Numbers——数位dp

题意：

给定区间【l，r】，问区间【l，r】中有多少满足条件的数字。对于一个数字x，若x的二进制表示中0的个数大于等于1的个数，那么x是满足条件的

思路：

将给定的数字x用二进制表示，用dp[i][j]表示前i位（0的数量-1的数量<=j）的数字总数，状态转移就很好写了，具体参见代码。

注意：

1.忽略前导0。

2.j有可能是负数，要简单hash一下，+32就可以

#include #include #include #include using namespace std;int num[100];int dp[100][100];int dfs(int pos, int state, bool limit, bool lead) { if (pos == 0) return (state >= 32); if (!limit && !lead && ~dp[pos][state]) return dp[pos][state]; int up = limit ? num[pos] : 1; int ans = 0; for (int i = 0; i <= up; i++) { if (lead && i == 0) ans += dfs(pos-1, state, limit && i==num[pos], lead && i==0); else ans += dfs(pos-1, state+(i==0?1:-1), limit && i==num[pos], lead && i==0); } if (!limit && !lead) dp[pos][state] = ans; return ans;}int solve(int n) { int pos = 0; while (n) { num[++pos] = n % 2; n /= 2; } return dfs(pos, 32, true, true);}int main() { memset(dp, -1, sizeof(dp)); int x, y; while (~scanf("%d%d", &x, &y)) { printf("%d\n", solve(y) - solve(x-1)); } return 0;}

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