P2392 考前临时抱佛脚
题目背景
kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。
题目描述
这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s*1,
s
2,
s
3,
s
4 道题目，完成每道题目需要一些时间，可能不等（
A
1,
A
2,…,A
s1
，
B
1,
B
2,…,B
s2
，
C
1,
C
2,…,C
s3
，
D
2,…,D
s4
）。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入格式
本题包含 55 行数据：第 11 行，为四个正整数 �1,�2,�3,�4
s
1,
s
2,
s
3,
s
4。
第 22 行，为
A
1,
A
2,…,A
s1
共s1 个数，表示第一科习题集每道题目所消耗的时间。
第 33 行，为
B
1,
B
2,…,B
s2
共 s2 个数。
第 44 行，为
C
1,
C
2,…,C
s3
共 s3 个数。
第 55 行，为
D
2,…,D
s4
共 s4 个数，意思均同上。
输出格式
输出一行,为复习完毕最短时间。
输入输出样例
输入 #1
复制
1 2 1 3
5
4 3
6
2 4 3
输出 #1
复制
20
说明/提示
1≤
s
1,
s
2,
s
3,
s
4≤20。
1≤
A
1,
A
2,…,A
s1
,
B
1,
B
2,…,B
s2
,
C
1,
C
2,…,C
s3
,
D
1,
D
2,…,D
s4
≤60。
题解：
这题是我认为，用递归进行暴力枚举的好题。让笔者更理解了暴力。
思路
对于每一道题，都可以用左脑或者右脑来进行。那么我们的思路就是吧每一道题左脑和右脑都尝试就行了。
模板
有了思路可能是最简单的一步，因为现在还要涉及到写出来。
- 确定递归的变量，步长，终止长度，左右脑的运算时长。
- 当现在的步长等于终止长度，就进行判断。现在的消耗的时间是不是最短的。
代码
#include<iostream>
using namespace std;
int ans = 0, s[5], t[5][21], mark[5] = {0, 1200, 1200, 1200, 1200} ;//记录5科的题目数量，以及对应消耗的时间
//mark消耗的最长时间20 * 60比这个大就可以了，不用太细致
void f(int left, int right, int step, int n){//左右脑时长、步长、终止长度
if (step == s[n]){//步长与终止长度相等
int temp = max(left, right);//判断消耗的时间
mark[n] = min(mark[n], temp);//判断是不是答案
return ;
}
step++;
f(t[n][step] + left, right, step, n);//这题用左脑
f(left, t[n][step] + right, step, n);//这题用右脑
}
int main(){
for (int i = 1; i <= 4; i++) cin >> s[i];
for (int i = 1;i <=4; i++){
for (int j = 1; j <= s[i]; j++){
cin >> t[i][j];
}
}//初始化
for (int i = 1; i <= 4; i++){
f(0, 0, 0, i);
ans += mark[i];//吧每科的最佳消耗时长相加
}
cout << ans << endl;//即可得出答案
}
最后
如果对你有帮助，点个赞和收藏呗！