kkksc03考前临时抱佛脚
题目背景
kkksc03 的大学生活非常的颓废,平时根本不学习。但是,临近期末考试,他必须要开始抱佛脚,以求不挂科。
题目描述
这次期末考试,kkksc03 需要考 $4$ 科。因此要开始刷习题集,每科都有一个习题集,分别有 $s_1,s_2,s_3,s_4$ 道题目,完成每道题目需要一些时间,可能不等($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}$)。
kkksc03 有一个能力,他的左右两个大脑可以同时计算 $2$ 道不同的题目,但是仅限于同一科。因此,kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug,因此他希望尽快把事情做完,所以他希望知道能够完成复习的最短时间。
输入格式
本题包含 $5$ 行数据:第 $1$ 行,为四个正整数 $s_1,s_2,s_3,s_4$。
第 $2$ 行,为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数,表示第一科习题集每道题目所消耗的时间。
第 $3$ 行,为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。
第 $4$ 行,为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。
第 $5$ 行,为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数,意思均同上。
输出格式
输出一行,为复习完毕最短时间。
样例 #1
样例输入 #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$。
```
记得优化优化!!!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
/** 以下为快读 **/
static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer in;
// 在没有其他输入时返回 null
static String next() {
try {
while (in == null || !in.hasMoreTokens())
in = new StringTokenizer(r.readLine());
return in.nextToken();
} catch (Exception e) {
}
return null;
}
static int nextInt() {
return Integer.parseInt(next());
}
static double nextDouble() {
return Double.parseDouble(next());
}
static long nextLong() {
return Long.parseLong(next());
}
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static final int N = 2510;
static int[] s = new int[N];
static int[] time = new int[N];
static int[] f = new int[N];
static int tot;
public static void main(String[] args) throws Exception{
for(int i = 1;i <= 4;i ++) {
s[i] = nextInt();//每一科的作业数量
}
for(int i = 1;i <= 4;i ++) {
int sum = 0;
for(int j = 1;j <= s[i];j ++) {
time[j] = nextInt();//每一个作业需要的时间
sum += time[j];
}
for(int j = 1;j <= s[i];j ++) {
for(int k = sum / 2;k >= time[j];k --) {//作业分两拨,一波<=sum/2 一波>=sum/2 求小的那波的最大值
f[k] = Math.max(f[k], f[k - time[j]] + time[j]);
}
}
tot += sum - f[sum / 2];
f = new int[N];
time = new int[N];
}
out.print(tot);
out.flush();
out.close();
}
}
``