【洛谷】P2392 kkksc03考前临时抱佛脚

【洛谷】P2392 kkksc03考前临时抱佛脚 题目地址：

https://www.luogu.com.cn/problem/P2392

题目背景：
kkksc03的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述：
这次期末考试，kkksc03需要考 4 4 4科。因此要开始刷习题集，每科都有一个习题集，分别有 s 1 , s 2 , s 3 , s 4 s_1,s_2,s_3,s_4 s1​,s2​,s3​,s4​道题目，完成每道题目需要一些时间，可能不等（ A 1 , A 2 , … , A s 1 A_1,A_2,ldots,A_{s_1} A1​,A2​,…,As1​​， B 1 , B 2 , … , B s 2 B_1,B_2,ldots,B_{s_2} B1​,B2​,…,Bs2​​， C 1 , C 2 , … , C s 3 C_1,C_2,ldots,C_{s_3} C1​,C2​,…,Cs3​​， D 1 , D 2 , … , D s 4 D_1,D_2,ldots,D_{s_4} D1​,D2​,…,Ds4​​）。
kkksc03有一个能力，他的左右两个大脑可以同时计算 2 2 2道不同的题目，但是仅限于同一科。因此kkksc03必须一科一科的复习。由于kkksc03还急着去处理洛谷的bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式：
本题包含 5 5 5行数据：第 1 1 1行，为四个正整数 s 1 , s 2 , s 3 , s 4 s_1,s_2,s_3,s_4 s1​,s2​,s3​,s4​。
第 2 2 2行，为 A 1 , A 2 , … , A s 1 A_1,A_2,ldots,A_{s_1} A1​,A2​,…,As1​​​共 s 1 s_1 s1​个数，表示第一科习题集每道题目所消耗的时间。
第 3 3 3行，为 B 1 , B 2 , … , B s 2 B_1,B_2,ldots,B_{s_2} B1​,B2​,…,Bs2​​​共 s 2 s_2 s2​个数。
第 4 4 4行，为 C 1 , C 2 , … , C s 3 C_1,C_2,ldots,C_{s_3} C1​,C2​,…,Cs3​​​共 s 3 s_3 s3​个数。
第 5 5 5行，为 D 1 , D 2 , … , D s 4 D_1,D_2,ldots,D_{s_4} D1​,D2​,…,Ds4​​个数，意思均同上。

输出格式：
输出一行，为复习完毕最短时间。

数据范围：
1 ≤ s 1 , s 2 , s 3 , s 4 ≤ 20 1leq s_1,s_2,s_3,s_4leq 20 1≤s1​,s2​,s3​,s4​≤20。
1 ≤ A 1 , A 2 , … , A s 1 , B 1 , B 2 , … , B s 2 , C 1 , C 2 , … , C s 3 , D 1 , D 2 , … , D s 4 ≤ 60 1leq A_1,A_2,ldots,A_{s_1},B_1,B_2,ldots,B_{s_2},C_1,C_2,ldots,C_{s_3},D_1,D_2,ldots,D_{s_4}leq60 1≤A1​,A2​,…,As1​​,B1​,B2​,…,Bs2​​,C1​,C2​,…,Cs3​​,D1​,D2​,…,Ds4​​≤60。

每门课可以分开考虑。对于每门课，要最小化耗时，就是要将这一课的习题分成两块，使得耗时大的那块的耗时尽可能小，显然要尽可能接近总耗时的一半才行，由此想到利用背包问题的求解办法，求不超过总耗时一半的情况下，最大的耗时组合，这样总耗时减去这个最大耗时组合的耗时，就是这门课的最少耗时。四门课加起来即可。代码如下：

#include 
#include 
using namespace std;

const int N = 30, M = N * 60;
int n[4];
int a[N], f[M];
int res;

int main() {
    for (int t = 1; t <= 4; t++)
        scanf("%d", &n[t]);

    for (int t = 1; t <= 4; t++) {
        int sum = 0;
        for (int i = 1; i <= n[t]; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }

        memset(f, 0, sizeof f);
        for (int i = 1; i <= n[t]; i++)
            for (int j = sum / 2; j >= a[i]; j--)
                f[j] = max(f[j], f[j - a[i]] + a[i]);

        res += sum - f[sum / 2];
    }

    printf("%dn", res);

    return 0;
}

时间复杂度 O ( ∑ i = 1 4 ( s i ∑ j = 1 s i t j ) ) O(sum_{i=1}^4( s_isum_{j=1}^{s_i} t_j)) O(∑i=14​(si​∑j=1si​​tj​))，空间 O ( max ⁡ i ∑ j = 1 s i t j ) O(max_i sum_{j=1}^{s_i} t_j) O(maxi​∑j=1si​​tj​)。