60 lines
1.9 KiB
C++
60 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
int res; //每一科目试题时间总和
|
||
int s[20 + 10]; //科目数量
|
||
int a[60 + 10]; //每一道题目需要的时间
|
||
|
||
int n; //当前科目的试题数量
|
||
int m; //当前科目完成试题的最短时间
|
||
|
||
/**
|
||
* 功能：本科目的试题，dfs跑所有情况。
|
||
* @param ans 当前选择路线上的时间长度值
|
||
* @param step 正在处理第几个试题
|
||
* @param cnt 当前科目一共多少个试题
|
||
*/
|
||
void dfs(int step, int ans) {
|
||
//step从站在1位置开始，向下一个位置进行眺望，如果已经站在n的位置上了，就表示该进行总结了~
|
||
if (step == n + 1) {
|
||
//如果ans代表前一半的话，那么res-ans就代表另一半，这两半谁大就是这组方案的解
|
||
m = min(m, max(ans, res - ans));//找出方案的最小值
|
||
return;
|
||
}
|
||
//不要下一道题
|
||
dfs(step + 1, ans);
|
||
//要上下一道题
|
||
dfs(step + 1, ans + a[step + 1]);
|
||
}
|
||
|
||
int main() {
|
||
//读入四科的题目数量
|
||
for (int i = 1; i <= 4; i++) cin >> s[i];
|
||
int sum = 0;
|
||
|
||
//遍历每一科，进行试题处理
|
||
for (int i = 1; i <= 4; i++) {
|
||
//本科目的所有试题总时长
|
||
res = 0;
|
||
//初始化数组
|
||
memset(a, 0, sizeof a);
|
||
//读入试题需要的时间
|
||
for (int j = 1; j <= s[i]; j++) {
|
||
cin >> a[j];
|
||
res += a[j];//计算总的时长
|
||
}
|
||
//当前科目的试题数量
|
||
n = s[i];
|
||
//逐科目开始找出最短的复习时间
|
||
m = INF;//预求最小，先设最大
|
||
//暴搜
|
||
dfs(1, 0);
|
||
//暴搜的结果在m里，把m加到总和中
|
||
sum += m;
|
||
}
|
||
//输出总和
|
||
cout << sum << endl;
|
||
return 0;
|
||
}
|