P2392 kkksc03考前临时抱佛脚
P2392 kkksc03考前临时抱佛脚 - 洛谷
题目背景
kkksc03的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。
题目描述
这次期末考试，kkksc03需要考4科。因此要开始刷习题集，每科都有一个习题集，分别有s1，s2，s3，s4道题目，完成每道题目需要一些时间，可能不等（A1,A2,⋯,As1，B1,B2,⋯,Bs2，C1,C2,⋯,Cs3，D1,D2,⋯,Ds4）。
kkksc03有一个能力，他的左右两个大脑可以同时计算2道不同的题目，但是仅限于同一科。因此，kkksc03必须一科一科的复习。
由于kkksc03还急着去处理洛谷的bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入格式
本题包含5行数据：
- 第1行，为四个正整数s1，s2，s3，s4。
- 第2行，为A1,A2,⋯,As1共s1个数，表示第一科习题集每道题目所消耗的时间。
- 第3行，为B1,B2,⋯,Bs2共s2个数。
- 第4行，为C1,C2,⋯,Cs3共s3个数。
- 第5行，为D1,D2,⋯,Ds4共s4个数，意思均同上。
输出格式
输出一行，为复习完毕最短时间。
输入输出样例
| 输入#1 | 输出#1 |
|---|---|
| 1 2 1 3 5 4 2 6 2 4 3 | 20 |
说明/提示
1≤s1,s2,s3,s4≤20。
1≤A1,A2,⋯,As1，B1,B2,⋯,Bs2，C1,C2,⋯,Cs3，D1,D2,⋯,Ds4≤60。
思路：
代码：
#include <bits/stdc++.h>
using namespace std;
int a[25], b[25], c[25], d[25];
bool dp[25][10000];
int fun(int times[], int n)
{memset(dp,false,sizeof(dp));int total = 0;for (int i = 1; i <= n; ++i) total += times[i];if (total == 0) return 0; int target = total / 2;dp[0][0] = true; for (int i = 1; i <= n; ++i) //前i个元素 {for (int j = 0; j <= target; ++j) // 遍历所有可能的和j{dp[i][j] = dp[i-1][j]; // 不选第i个元素：继承前i-1个元素的状态if (j >= times[i] && dp[i-1][j - times[i]]) // 选第i个元素（当j >= t时） {dp[i][j] = true; // 只要有一个情况为true，当前状态为true}} }int max_sub = 0;for (int j = target; j >= 0; --j) {if (dp[n][j]) {max_sub = j;break;}}return total - max_sub;
}int main() {int s1, s2, s3, s4;cin >> s1 >> s2 >> s3 >> s4;for (int i = 1; i <= s1; ++i) cin >> a[i];for (int i = 1; i <= s2; ++i) cin >> b[i];for (int i = 1; i <= s3; ++i) cin >> c[i];for (int i = 1; i <= s4; ++i) cin >> d[i];// 计算并输出总时间int total_time = fun(a, s1) + fun(b, s2) + fun(c, s3) + fun(d, s4);cout << total_time << endl;return 0;
}