题目链接
题目简介：
淘汰赛分 主淘汰赛 和 次淘汰赛：
主淘汰赛有 c 个问题，每轮产生 n 个获胜者
次淘汰赛有 d 个问题，每轮产生 1 个获胜者
需要从两种淘汰赛中选出 n*m 个选手参加总决赛
并且有 k 个往届总决赛的获奖选手不需参加淘汰赛即可进入总决赛
问通过组织以上两种淘汰赛选出 n*m 名选手（含往届的 k 名选手）参加总决赛所需问题的最少数目
典型的完全背包问题
java实现如下：
import java.util.Scanner;
public class Main {
static int c, d, n, m, k, v, dp[];
//完全背包
static void f_full(int cost, int val) {
for (int i = cost; i <= v; i++)
dp[i] = Math.max(dp[i], dp[i - cost] + val);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
c = sc.nextInt();
d = sc.nextInt();
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
int temp = n * m;
if (k < temp) {
//预设可取的背包空间
v = Math.min(c * m, temp * d);
dp = new int[v + 1];
//初始化dp[0]为k
dp[0] = k;
//只有两种方案
f_full(c, n);
f_full(d, 1);
int i = 1;
for (; i <= v; i++) {
if (dp[i] >= temp)
break;
}
System.out.println(i);
} else
System.out.println(0);
}
}
