首页 > 代码库 > POJ 3252 数位DP
POJ 3252 数位DP
链接：
http://poj.org/problem?id=3252
题意：
给你一个区间l，r，求区间中有多少个数转化为二进制后1的个数大于等于0的个数
题解：
还是数位dp，不过多了前导0的判断
代码：
31 int a[40];32 int dp[40][80];33 34 int dfs(int pos, int sta, bool lead, bool limit) {35 if (pos == -1) return sta >= 40;36 if (!lead && !limit && dp[pos][sta] != -1) return dp[pos][sta];37 int up = limit ? a[pos] : 1;38 int res = 0;39 rep(i, 0, up + 1) {40 if (lead && i == 0) res += dfs(pos - 1, sta, lead, limit && i == a[pos]);41 else res += dfs(pos - 1, sta + (i == 0 ? 1 : -1), false, limit && i == a[pos]);42 }43 if (!lead && !limit) dp[pos][sta] = res;44 return res;45 }46 47 int solve(int x) {48 int pos = 0;49 while (x) {50 a[pos++] = x & 1;51 x >>= 1;52 }53 return dfs(pos - 1, 40, true, true);54 }55 56 int main() {57 int l, r;58 cin >> l >> r;59 memset(dp, -1, sizeof(dp));60 cout << solve(r) - solve(l - 1) << endl;61 return 0;62 }
POJ 3252 数位DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。