原题链接:开心的金明
解题思路:
应该是用dp做的,然而并不会...强行DFS还是可以过的,可以承受20以内数据量的打击
注意事项:
哪个大佬来教我一下dp哈
参考代码:
#include <iostream> #define N 25 using namespace std; int importance[N + 2]; int value[N + 2]; void DFS(int curIndex, int curValue, long long curProduct, const int n, const int maxValue, long long & maxProduct) { if (curIndex >= n) { if (curProduct > maxProduct && curValue <= maxValue) { maxProduct = curProduct; } return; } else if(curValue > maxValue) { return; } else { DFS(curIndex + 1, curValue + value[curIndex], curProduct + importance[curIndex] * value[curIndex], n, maxValue, maxProduct); DFS(curIndex + 1, curValue, curProduct, n, maxValue, maxProduct); } return; } int main(int argc, char** argv) { int n = 0, m = 0; cin >> n >> m; int v = 0, p = 0; for (int i = 0; i < m; i++) { cin >> v >> p; value[i] = v; importance[i] = p; } long long ans = 0; DFS(0, 0, 0, m, n, ans); cout << ans << endl; return 0; }
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复