关注
/*
dfs实际上是个模拟
*/
//len表示判断的是哪一位
ll dfs(ll len,int maxi,int k,int f){
//dp[len][k][f]存储的是到长度为len为止,第k位为0和第k位为1的数是多少
//maxi标志的是上一位模拟的数是不是等于num的这一位的数
/*
我们还是拿100来举例子,因为最高位我们得到的一定为1,所以传进来的时候maxi就是1
那么我们第一位既可以模拟0也可是模拟1
模拟0的时候,i != a[len]所以maxi = false,之后也都是false
我们下一位就可以模拟00X跟01X,剩下的类似
模拟1的时候,i == a[len]所以maxi = true
我们就可以模拟1XX
但是由于这时a[2] = 0所以只能模拟10X
差不多就已经很清楚了
*/
//dp[len][k][f]这里其实就是记忆化搜索,如果之前出现过,就直接返回结果就好。
if(dp[len][k][f] != -1 && maxi == 0)
return dp[len][k][f];
//只有当第k位为1的情况这里才会加上1
if(!len)
return f;
ll cnt = 0;
int maxn = maxi ? a[len] : 1;
//i这里代表着第len位的数字是多少
//那么f||len == k && i就是判断这次模拟的数的第k位是否为1
for(int i = 0;i <= maxn;i++){
cnt += dfs(len - 1,maxi && i == a[len],k,f||len == k&&i);
}
//只有当maxi等于false的时候,我们模拟了下一位为0,1的全部情况,此时才更新dp的值
//表示不受之前的数的限制,所求的只是[0,1 << (len) - 1]]满足条件的数
return maxi ? cnt : dp[len][k][f] = cnt;
}
//二进制拆分数位,返回的结果是第k位为1的数总共有几个
ll div(ll num,int k){
memset(a,0,sizeof(a));
int index = 0;
while(num){
a[++index] = num % 2;
num /= 2;
}
return dfs(index,1,k,0);
}
E题最简单数位DP标程,本菜鸡的一点个人解读,希望可以帮到跟我一样的萌新新理解,个人一点愚见,如果有不正确的地方,还请大佬们们斧正ORZ
查看原帖
5 评论
相关推荐
牛客49896997...:电话都漏出来,要保护个人隐私,我先来,你说我见过最美的牛客女孩 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
14639次浏览 168人参与
# 记录实习开销 #
183091次浏览 732人参与
# 牛客AI体验站 #
17974次浏览 305人参与
# 大家每天通勤多久? #
82162次浏览 597人参与
# 正在实习的你,几点下班 #
295509次浏览 1971人参与
# 牛客租房专区 #
152444次浏览 1520人参与
# 你小时候最想从事什么职业 #
154094次浏览 2059人参与
# 有转正机会的小厂实习值得去吗? #
962次浏览 21人参与
# 不给转正的实习,你还去吗 #
2624553次浏览 22813人参与
# 你最讨厌面试被问什么 #
1720次浏览 27人参与
# 你觉得今年秋招难吗 #
1988340次浏览 18492人参与
# 如何缓解入职前的焦虑 #
259245次浏览 1454人参与
# 校招入职后的感受 #
487816次浏览 3681人参与
# 金融银行求职进展汇总 #
309524次浏览 1685人参与
# 国庆放假,你还会投简历吗? #
47858次浏览 214人参与
# 秋招的破防瞬间 #
509216次浏览 2606人参与
# 毕业论文进行时 #
29063次浏览 156人参与
# 春节回家,你最想让 AI 帮你解决哪件事? #
925次浏览 19人参与
# 这份实习,有没有动摇过你的职业方向? #
2501次浏览 40人参与
# 毕业后不工作的日子里我在做什么 #
239332次浏览 1697人参与
查看20道真题和解析