洛谷-P2392 kkksc03考前临时抱佛脚

洛谷 搜索

---

原题链接

题目背景

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

题目描述

这次期末考试，kkksc03 需要考4科。因此要开始刷习题集，每科都有一个习题集，分别有 $s1,s2,s3,s4s_1,s_2,s_3,s_4s1​,s2​,s3​,s4​$ 道题目，完成每道题目需要一些时间，可能不等$（A1,A2,…,As1A_1,A_2,\ldots,A_{s_1}A1​,A2​,…,As1​​，B1,B2,…,Bs2B_1,B_2,\ldots,B_{s_2}B1​,B2​,…,Bs2​​，C1,C2,…,Cs3C_1,C_2,\ldots,C_{s_3}C1​,C2​,…,Cs3​​，D1,D2,…,Ds4D_1,D_2,\ldots,D_{s_4}D1​,D2​,…,Ds4​​）$

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

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

输入格式

本题包含 5 行数据：第1行，为四个正整数 $s1,s2,s3,s4s_1,s_2,s_3,s_4s1​,s2​,s3​,s4​$

第 2 行，为 $A1,A2,…,As1A_1,A_2,\ldots,A_{s_1}A1​,A2​,…,As1​​$ 共$s_1$个数，表示第一科习题集每道题目所消耗的时间。

第 3 行，为 $B1,B2,…,Bs2B_1,B_2,\ldots,B_{s_2}B1​,B2​,…,Bs2$​​ 共 $s_2$ 个数。

第 4 行，为 $C1,C2,…,Cs3C_1,C_2,\ldots,C_{s_3}C1​,C2​,…,Cs3$​​ 共 $s_3$​ 个数。

第 5 行，为 $D1,D2,…,Ds4D_1,D_2,\ldots,D_{s_4}D1​,D2​,…,Ds4$​​ 共 $s_4$​ 个数，意思均同上。

输出格式

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

输入 #1

1 2 1 3     
5
4 3
6
2 4 3

输出 #1

20

说明/提示

$1\leq s_1,s_2,s_3,s_4\leq 20$

$$1\leq 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

(暴搜) $O(2^n)$

数据量是20所以直接暴力枚举，$2^n$也不会超时

用时 81ms 结果

C++代码

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <iostream>
#include <algorithm>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d", &n)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define fs first
#define se second
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
int s[5], a[21], sum, ans, l ,r;
void search(int i,int x)
{
    if(i > x) 
    {
        sum = min(sum, max(l,r));
        return;
    }
    //回溯
    l += a[i];
    search(i+1,x);
    l -= a[i];
    r += a[i];
    search(i+1,x);
    r -= a[i];
}
int main()
{
    rep(i, 1, 4) cin >> s[i];
    rep(i, 1, 4)
    {
        l = r = 0;
        sum = INF;
        rep(j, 1, s[i])
            cin >> a[j];
        search(1, s[i]);
        ans += sum;
    }
    cout << ans;
    return 0;
}

---

算法2

(DP) $O(nlogn)$

时间是体积，也是价值，对于每一门课有n个物品，体积为sum/2（sum为时间总和）的01背包即可。

用时 30ms 结果

C++代码

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <iostream>
#include <algorithm>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d", &n)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define fs first
#define se second
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
int s[5], sum, a[21], ans;
int dp[N];
int main()
{
    rep(i, 1, 4) cin >> s[i];
    rep(i, 1, 4)
    {
        sum = 0;    //时间总和
        memset(dp, 0, sizeof dp);
        rep(j, 1, s[i])
        {
            cin >> a[j];
            sum += a[j];
        }
        rep(k, 1, s[i])
            for(int j = sum/2; j >= a[k]; j--)
                dp[j] = max(dp[j], dp[j-a[k]] + a[k]);
        ans += max(dp[sum/2], sum - dp[sum/2]);
    }
    cout << ans;
    return 0;
}