2437: 【普及-】【P2392】考前临时抱佛脚
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
这次期末考试，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 calMaxTime(int n) {
for (int S=0;S<(1<<n);S++) {
nowtime=0;
for (int i=0;i<n;i++) {
if (S&(1<<i)) nowtime+=a[i+1];
}
if (nowtime<=sum/2.0)
maxtime=max(maxtime,nowtime);
}
}
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]; //记录这科作业总耗时；
}
if (maxdeep==1)
ans+=a[1];
else if (maxdeep==2)
ans+=max(a[1],a[2]);
else {
maxtime=0;
calMaxTime(maxdeep);
ans += (sum-maxtime); //加上答案
}
}
cout << ans;
return 0;
}