目录
- T1. 开餐馆
- T2. 糖果
-
- 思路分析
- T3. 鸡蛋的硬度
-
- 思路分析
- T4. 山区建小学
-
- 思路分析
T1. 开餐馆
此题为 2020 年 12 月四级第一题原题，见 2020 年 12 月青少年软编等考 C 语言四级真题解析中的 T1。
T2. 糖果
由于在维护世界和平的事务中做出巨大贡献，Dzx 被赠予糖果公司 2010 年 5 月 23 日当天无限量糖果免费优惠券。在这一天，Dzx 可以从糖果公司的 N N N 件产品中任意选择若干件带回家享用。糖果公司的 N N N 件产品每件都包含数量不同的糖果。Dzx 希望他选择的产品包含的糖果总数是 K K K 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx 最多能带走多少糖果呢？注意：Dzx 只能将糖果公司的产品整件带走。
时间限制：7 s
内存限制：64 MB
- 输入
第一行包含两个整数 N ( 1 ≤ N ≤ 100 ) N\ (1\le N\le 100) N (1≤N≤100) 和 K ( 1 ≤ K ≤ 100 ) K\ (1\le K\le 100) K (1≤K≤100)。
以下 N N N 行，每行 1 1 1 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 1000000 1000000 1000000。 - 输出
符合要求的最多能达到的糖果总数，如果不能达到 K K K 的倍数这一要求，输出 0 0 0。 - 样例输入
5 7 1 2 3 4 5 - 样例输出
14 - 提示
Dzx 的选择是 2 + 3 + 4 + 5 = 14 2+3+4+5=14 2+3+4+5=14，这样糖果总数是 7 7 7 的倍数，并且是总数最多的选择。
思路分析
此题考查动态规划中的背包问题，属于基础题。
容易想到定义 f i , j f_{i,j} fi,j 表示前 i i i 种糖果是否可以获得总数 j j j 颗糖果，然后从大到小遍历状态数组，找到最大且满足是 k k k 的倍数的 j j j 即为答案，但是糖果的总数最多为 1 0 8 10^8 108，会导致空间和时间超限。
根据题目描述，我们需要求出糖果总数是 k k k 的倍数的结果，于是我们可以只记录糖果总数在 m o d k \bmod\ k mod k 的状态下可以获得的最大值，于是定义 f i , j f_{i,j} fi,j 表示前 i i i 种糖果在总数 m o d k = j \bmod\ k = j mod k=j 的状态下可以获得的最大值，容易得到状态转移方程为
f i , j = max { f i − 1 , j , f i − 1 , ( j − ( a i m o d k ) ) m o d k + a i } f_{i,j} = \max\{f_{i-1,j}, f_{i-1, (j-(a_i\bmod k)) \bmod k} + a_i\} fi,j=max{
fi−1,j,fi−1,(j−(aimodk))modk+ai}
此题询问的是恰好满足的情况，因此初始值为 f i
