P2392 kkksc03考前临时抱佛脚：01背包思想

本文主要是介绍P2392 kkksc03考前临时抱佛脚：01背包思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题链接：P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

  由于左右脑可以同时计算两个题，，因此可以想到， 每个题都有分给左脑还是右脑两种选择  ，对于一个问题，一个子问题有两种选择，都可以采用01背包思想，由于本人对dp不是很熟练，因此采用dfs + 剪枝

代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int s[5][30];
int n[5];
int res = 0;
int minT = 10000010;
int l = 0, r = 0;void dfs(int x, int y) {//全遍历完了if (y == n[x] ) {minT = min(minT, max(l, r));return;}l += s[x][y];dfs(x, y + 1);l -= s[x][y];r += s[x][y];dfs(x, y + 1);r -= s[x][y];
}int main() {cin >> n[1] >> n[2] >> n[3] >> n[4];for (int i = 1; i <= 4; i++) {for (int j = 0; j < n[i]; j++) cin >> s[i][j];minT = 10000010;l = 0, r = 0;dfs(i, 0);res += minT;}cout << res;return 0;
}

以上是本文全部内容，如果对你有帮助点个赞再走吧~  ₍˄·͈༝·͈˄*₎◞ ̑̑

这篇关于P2392 kkksc03考前临时抱佛脚：01背包思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---