题目类型 DP
题目意思
给出一个数字区间 问这个区间内有多少个数 满足以下条件
二进制表示下 0 的个数大于或等于 1 的个数
解题方法
数位DP
用 dp[pos][n0][n1] 表示当前处在第 pos 位 (从高位到低位) 0 的个数为n0(前缀0不算) 1 的个数为 n1 且当前位的取值没限制时的合法数字的总数
无限制的意思是 如果要求区间 [0, 123] 之间有多少个合法数字 那么当最高位为 1 时 次高位的取值就只能是 0->2 了 如果为3 就是130+了
记忆化搜索 即可快速求得结果
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int num[100], k;
int dp[32][32][32];
int DFS(int pos, int n0, int n1, bool bound) {
if(pos == 0) { 如果后面已经没有位数了就根据 0 的个数和 1 的个数返回正确的值
if(n0 >= n1) return 1;
else return 0;
}
if(bound == 0 && dp[pos-1][n0][n1] != -1) return dp[pos-1][n0][n1]; // 记忆化优化
int sum = 0;
int end = bound ? num[pos-1] : 1; // end 是当前位能取得到的最大值
for( int i=0; i<=end; i++ ) {
if(i == 0) sum += DFS(pos - 1, n0+(n1!=0), n1, bound && i == end);//如果当前位取值有限制且这位上的数字又取到了边界值 则下一位有限制
else sum += DFS(pos - 1, n0, n1+1, bound && i == end);
}
if(bound == false) dp[pos-1][n0][n1] = sum;
return sum;
}
int Solve(int n) {
k = 0;
while(n) {
num[k++] = n % 2;
n /= 2;
}
return DFS(k, 0, 0, 1);
}
int main() {
int s, e;
memset(dp, -1, sizeof(dp)); // 只需要初始化一次 因为这个 dp数组都是当前位取值无限制下的结果
while(scanf("%d%d", &s, &e) != EOF) {
int ans = Solve(e);
ans -= Solve(s-1); // 数位dp一般是直接求出 0->N的合法数字 那么 s->t的合法数字就是 Solve(0->t) - Solve(0-> s-1)
printf("%d\n", ans);
}
return 0;
}