解题思路:dp[i,j]代表前i个砝码能否称出j这个重量,而dp[i,j]取决与三个量:max(dp[i - 1][j], max(dp[i - 1][j + w[i]], dp[i - 1][abs(j - w[i])]));
若前i - 1个砝码能称出j + w[i]的重量,因为第i个砝码重量为w[i],那么想要称出j重量只要把第i个砝码放在称物品的一侧,
即左边:j重量的物体 + w[i] == 从前i- 1个砝码匹配出j + w[i]的重量(假设dp[i - 1][j] = 1)
dp[i - 1][abs(j - w[i])])同理,
三个量只要有一个值为1即可,简单取一下最大值dp[i,j]能取到1即前i个能称出j
注意事项:重量j从0开始迭代,因为会影响到需要的dp[i][0]的决策
参考代码:
#include#includeusing namespace std; int dp[105][100000]; int n, w[105], sum, ans; int main(){ cin>>n; for(int i = 1; i >w[i]; sum += w[i]; } dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 0; j <= sum; j++){ dp[i][j] = max(dp[i - 1][j], max(dp[i - 1][j + w[i]], dp[i - 1][abs(j - w[i])])); } } for(int i = 1; i <= sum; i++){ if(dp[n][i]){ ans++; } } cout<<ans; return 0; }
0.0分
16 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复