首页 > 代码库 > POJ 3252 Round Numbers(数位dp)
POJ 3252 Round Numbers(数位dp)
题意:给定区间[l,r],l < r ,求区间中满足条件的正整数的个数:二进制表示下0的个数不少于1的个数。
分析:f(x)表示<=x时满足条件的数的个数,所求问题即为f(r)-f(l-1)。x二进制表示下从高到低位为1,bi,bi-1, bi-2, b0, 长度为len, 那么f(x)可以这样求解:
dp[i][j]表示从i~0位可以任意为0或1时,0的个数比1多j个情况,由于j可能为负数,所以这里方便处理,将j = 40表示0的个数和1的个数一样多。
转移:dp[i][j] = sum{dp[i-1][j-1]+dp[i-1][j+1]}.
1首先考虑长度<len的数,设长度l < len,由于首位一定为1,那么只需考虑剩下的l-1位任意选取时的情况;
2考虑长度为len的数,首位一定为1,从次高位到低位一次考虑,如果bi为1,那么此位为0,之前的位数和1,bi+2, bi+1一样时,剩下的i-1,i-2, 0位便可任意选取。
最后应该考虑x本身是否满足条件。
代码:
1 #include <cstdio> 2 #include <iostream> 3 #include <map> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #define pb push_back 8 #define mp make_pair 9 #define esp 1e-810 #define lson l, m, rt<<111 #define rson m+1, r, rt<<1|112 #define sz(x) ((int)((x).size()))13 #define pb push_back14 #define in freopen("solve_in.txt", "r", stdin);15 #define bug(x) printf("Line : %u >>>>>>\n", (x));16 #define inf 0x7f7f7f7f17 using namespace std;18 typedef long long LL;19 typedef map<int, int> MPS;20 typedef pair<int, int> PII;21 22 const int maxn = 33;23 int dp[maxn][100], dig[maxn];24 int solve(int x) {25 if(!x) return 0;26 int len = 0, ans = 0;27 while(x) {28 dig[len++] = x&1;29 x >>= 1;30 }31 int tot = 0;32 for(int i = len-1; i >= 0; i--) {33 if(i < len-1) {34 if(i-1 >= 0)35 for(int j = 41; j < 100; j++)36 ans += dp[i-1][j];37 if(dig[i]) {38 if(i) {39 for(int j = max(1, 40-tot-1); j < 100; j++)40 ans += dp[i-1][j];41 } else {42 ans += (tot+1 >= 0);43 }44 }45 }46 tot += dig[i] ? -1 : 1;47 }48 ans += (tot >= 0);49 return ans;50 }51 void pre() {52 dp[0][41] = 1;53 dp[0][39] = 1;54 for(int i = 1; i < maxn; i++)55 for(int j = 1; j < 100; j++) {56 dp[i][j] += dp[i-1][j+1]+dp[i-1][j-1];57 }58 }59 int main() {60 61 int l, r;62 pre();63 scanf("%d%d", &l, &r);64 cout << solve(r)-solve(l-1) << endl;65 return 0;66 }
POJ 3252 Round Numbers(数位dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。