2024-09-05 17:44 已编辑 西安电子科技大学 C++ 发布于浙江
关注
小米笔试题解 9.5
第一题:分情况讨论，如何一台机器做两个面包，遍历ai和bi之和得到答案，如果是两台机器做，通过set来维护所有的bi，遍历机器，遍历到第u台机器就把bi从set里面扔掉，然后取set中的最小值和ai相加即可。
第二题:背包问题，首先把所有输入都余上X做预处理，同时输入过程中维护一个总和，这个总和取余之后可得最坏解法。二维dp，第一维i的意思是考虑前i个输入，第二维j的意思为在考虑前i个输入的情况下组合出j需要的最小代价，按状态转移即可。拿到最终的dp数组后，固定一维为n，遍历二维看看和X差多少对答案取其中最小即可。
补充转移方程
for(int i=1;i
for(int j=0;j
dp[i][j]=min(dp[i][j],dp[i-1][j]+1)//对应删除第i的情况
int tmp=(j-mem[i]+X)%X;
dp[i][j]=min(dp[i][j],dp[i-1][tmp])//对应采用第i个的情况
}
}
第二题:背包问题，首先把所有输入都余上X做预处理，同时输入过程中维护一个总和，这个总和取余之后可得最坏解法。二维dp，第一维i的意思是考虑前i个输入，第二维j的意思为在考虑前i个输入的情况下组合出j需要的最小代价，按状态转移即可。拿到最终的dp数组后，固定一维为n，遍历二维看看和X差多少对答案取其中最小即可。
补充转移方程
for(int i=1;i
for(int j=0;j
dp[i][j]=min(dp[i][j],dp[i-1][j]+1)//对应删除第i的情况
int tmp=(j-mem[i]+X)%X;
dp[i][j]=min(dp[i][j],dp[i-1][tmp])//对应采用第i个的情况
}
}
全部评论
chcicji
中国科学技术大学 C++
第一题为啥91啊
__nil
成都信息工程大学 后端
第二题看着有点像编辑距离，但是不会写
ccs12138
华东理工大学 机械工程师
有没有结构的
翻斗花园第一突击手吉吉
文华学院 Java
第一题 73 第二题看不懂直接输出 1 骗了 27
Yohifo
第一拖拉机制造厂拖拉机学院 C++
第一题用优先级队列A了，但第二题没想到用二维背包，还是太菜了
汪汪小乌拉
门头沟学院 Java
第二题我贪了40分钟你告诉我是dp😭😭😭
哈哈哈加油吧
南开大学 Java
第一题A，第二题动态规划方程写不出来，尝试删每一个数后再加，取最小值，过了55😂
菜鸡只啄我寄几
门头沟学院 Java
请问第二题的动态转移方程大概是什么样子的呀
凉宫春
门头沟学院 Java
int tmp=(j-mem[i]+X)%X;
mem[i] 是啥意思没看懂
相关推荐
01-14 20:42
南昌航空大学科技学院 前端工程师 
点赞 评论 收藏
分享
01-12 20:24
门头沟学院 后端 
点赞 评论 收藏
分享
查看8道真题和解析 点赞 评论 收藏
分享