1 条题解
-
0
题目分析
选取 个材料,不难想到如果想有解,就需要选取的 个材料魔力之和 满足以下条件
若想要达到 的时间尽可能短,那么在固定 的情况下,若有多种方案能够满足条件,一定是 越大越好,这样时间时最短的。因此,我们枚举每一个 ,在 固定的情况下,定义 来进行
dp,其中:表示现在考虑在前 种材料中选择, 表示已选材料的数量, 表示余数, 中记录最大的 值。
即 表示前 个材料中选择 个材料,使得选择的材料的魔力之和 取余数量 的值为 的最大的 值。
转移方程如下:
$$f_{i,j,k} = \max(f_{i-1,j,k},f_{i-1,j-1,(k+s-a_i\%s)\%s} + a_i)$$值得注意的是: 中第二项转移的前提是 可行,所以初始赋值时要注意。
最后答案统计就是
时间复杂度 。
- 1
信息
- ID
- 55
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者