2509: 【普及-】【P2392】kkksc03考前临时抱佛脚
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
这次期末考试，kkksc03 需要考 科。因此要开始刷习题集，每科都有一个习题集，分别有 道题目，完成每道题目需要一些时间，可能不等（，，，）。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入
本题包含 行数据：第 行，为四个正整数 。
第 行，为 共 个数，表示第一科习题集每道题目所消耗的时间。
第 行，为 共 个数。
第 行，为 共 个数。
第 行，为 共 个数，意思均同上。
输出
输出一行,为复习完毕最短时间。
样例输入 复制
1 2 1 3
5
4 3
6
2 4 3样例输出 复制
20提示
说明/提示
。
。
#include<bits/stdc++.h>
using namespace std;
int nowtime,maxtime,sum; //子集中的时间和、最大合法时间和、该课作业总和；
int ans,maxdeep; //答案，最深递归层数限制（改课作业数量）；
int s[4],a[21]; //每科作业数量，每个作业的耗时；
void dfs(int x) {
if (x>maxdeep) { //所有作业枚举完毕，达到了最大递归层数
maxtime=max(maxtime,nowtime); //如果解更优，更新答案；
return;
}
if (nowtime+a[x]<=sum/2) { //如果放入这个作业是合法的，选择它
nowtime+=a[x]; //增加子集中这道题目的时间
dfs(x+1); //下一层递归
nowtime-=a[x]; //去除掉子集中这道题目的时间
}
dfs(x+1); //不选这个题目，直接进行下一层递归
}
int main(){
cin>>s[0]>>s[1]>>s[2]>>s[3];
for (int i=0;i<4;i++) { //四种科目
nowtime = 0;
maxdeep = s[i];
sum = 0; //别忘了每次科目都要初始化；
for (int j=1;j<=s[i];j++) {
cin >> a[j];
sum += a[j]; //记录这科作业总耗时；
}
maxtime=0;
dfs(1); //开始枚举第一个题目
ans += (sum-maxtime); //加上答案
}
cout << ans;
return 0;
}