[数据结构与算法]P2392 kkksc03考前临时抱佛脚——dfs+剪枝

kkksc03考前临时抱佛脚

题目背景

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

题目描述

这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（$A_1,A_2,\dots ,A_{s_1}$，$B_1,B_2,\dots ,B_{s_2}$，$C_1,C_2,\dots ,C_{s_3}$，$D_1,D_2,\dots ,D_{s_4}$）。

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

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

输入格式

本题包含 $5$ 行数据：第 $1$ 行，为四个正整数 $s_1,s_2,s_3,s_4$。

第 $2$ 行，为 $A_1,A_2,\dots ,A_{s_1}$ 共 $s_1$ 个数，表示第一科习题集每道题目所消耗的时间。

第 $3$ 行，为 $B_1,B_2,\dots ,B_{s_2}$ 共 $s_2$ 个数。

第 $4$ 行，为 $C_1,C_2,\dots ,C_{s_3}$ 共 $s_3$ 个数。

第 $5$ 行，为 $D_1,D_2,\dots ,D_{s_4}$ 共 $s_4$ 个数，意思均同上。

输出格式

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

样例 #1

样例输入 #1

1 2 1 3		
5
4 3
6
2 4 3

样例输出 #1

20

提示

$1\le s_1,s_2,s_3,s_4\le 20$。

$1\le A_1,A_2,\dots ,A_{s_1},B_1,B_2,\dots ,B_{s_2},C_1,C_2,\dots ,C_{s_3},D_1,D_2,\dots ,D_{s_4}\le 60$。

分析

1. 由于总共才4科目，每个科目最多20题，所以本题可以爆搜，枚举各种情况；
2. 由于左脑右脑同时计算只能用在同一科目，所以我们逐个对每一科目进行搜索，在搜索每一个科目时，每个题既可以放在左脑，也可以放在右脑，所以我们对每种情况进行dfs，然后回溯回来，在递归出口也就是最后一题也搜完了，先max(l, r)这是当前方案完成作业的最少时间（因为要保证左右脑的作业全完成了），然后和以前的方案得到的minn取最优；
3. 搜索的实现流程简单说下，比如第一题，先放左脑，时间累加到L，然后dfs搜下一题（u+1就是搜下一题去了），下一题也是两种选择，也先放左脑，累加时间，再dfs下一题，同样…，当搜到最后一题return（此时是最后一题在左脑），然后回溯，也就是最后一题在右脑，然后判断完return，然后就回溯到倒数第二题在右脑，再去dfs到最后一题分别在左右脑…
4. 此题可以不剪枝也能过，但是数据量加大就可能tle，所以附上了剪枝，当当前方案的l或r任意一个比已经求得的最优解还大，就直接return;

#include<bits/stdc++.h>

using namespace std;

int s[5];
int tim[5][25];
int minn;//每个科目完成的最短时间
int ans;
int l, r;//左脑右脑

//sub:当前在第几个科目，u为当前方案该搜第几题了
void dfs(int sub, int u) {
    //剪枝
    if (l >= minn || r >= minn)
        return;

    if (u > s[sub]) {
        //max(l, r)这是当前方案完成作业的最少时间，然后和以前的方案得到的minn取最优
        minn = min(minn, max(l, r));
        return;
    }
    //第u个题给左脑
    l += tim[sub][u];
    dfs(sub, u + 1);
    l -= tim[sub][u];

    //第u个题给右脑
    r += tim[sub][u];
    dfs(sub, u + 1);
    r -= tim[sub][u];
}


int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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 >> tim[i][j];
        }
        l = 0, r = 0, minn = 100000;
        dfs(i, 1);
        ans += minn;
    }
    cout << ans;
    return 0;
}