🎈 原创

题目背景

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

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1A1,A2,…,A**s1，B1,B2,…,Bs2B1,B2,…,B**s2，C1,C2,…,Cs3C1,C2,…,C**s3，D1,D2,…,Ds4D1,D2,…,D**s4）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 55 行数据：第 11 行，为四个正整数 s1,s2,s3,s4s1,s2,s3,s4。

第 22 行，为 A1,A2,…,As1A1,A2,…,A**s1 共 s1s1 个数，表示第一科习题集每道题目所消耗的时间。

第 33 行，为 B1,B2,…,Bs2B1,B2,…,B**s2 共 s2s2 个数。

第 44 行，为 C1,C2,…,Cs3C1,C2,…,C**s3 共 s3s3 个数。

第 55 行，为 D1,D2,…,Ds4D1,D2,…,D**s4 共 s4s4 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

输入输出样例

输入 #1

1 2 1 3		
5
4 3
6
2 4 3

输出 #1

20

说明/提示

1≤s1,s2,s3,s4≤201≤s1,s2,s3,s4≤20。

1≤A1,A2,…,As1,B1,B2,…,Bs2,C1,C2,…,Cs3,D1,D2,…,Ds4≤601≤A1,A2,…,A**s1,B1,B2,…,B**s2,C1,C2,…,C**s3,D1,D2,…,D**s4≤60。

---

题解https://89568.blog.luogu.org/solution-p2392

这篇题解简直醍醐灌顶，第一次感受到动态规划的魅力。

将完成一个科目所有课程的总时间分成一半，在这一半时间内用动态规划来分析用这一半的时间最多能完成的作业的时间总和。可以理解成，用半边的大脑最多能完成多少。这个时间总是小于等于另一半大脑所需要的时间，即总和减去这个时间。所以要完成所有作业只要取较大的数即可。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;


int main(int argc, const char * argv[])
{
    int num[4];
    for(int i = 0; i < 4; i++)
        cin >> num[i];
    int ans = 0;
    for(int i = 0; i < 4; i++)
    {
        int homework[num[i]];
        int sum = 0;
        for(int j = 0; j < num[i]; j++)
        {
            cin >> homework[j];
            sum += homework[j];
        }
        int dp[sum / 2 + 1];
        memset(dp, 0, sizeof(dp));
        for(int j = 0; j < num[i]; j++)
            for(int k = sum / 2; k >= homework[j]; k--)
                dp[k] = max(dp[k], dp[k - homework[j]] + homework[j]);
        ans += sum - dp[sum / 2];
        
    }
    cout << ans << endl;
    
    return 0;
}