1 条题解

  • 0
    @ 2026-11-15 13:16:50

    题目分析

    选取 ss 个材料,不难想到如果想有解,就需要选取的 ss 个材料魔力之和 sumsum 满足以下条件

    m=sum mod sm = sum \bmod s

    若想要达到 mm 的时间尽可能短,那么在固定 ss 的情况下,若有多种方案能够满足条件,一定是 sumsum 越大越好,这样时间时最短的。因此,我们枚举每一个 ss,在 ss 固定的情况下,定义 fi,j,kf_{i,j,k} 来进行 dp,其中:

    ii 表示现在考虑在前 ii 种材料中选择,jj 表示已选材料的数量,kk 表示余数,ff 中记录最大的 sumsum 值。

    即 fi,j,kf_{i,j,k} 表示前 ii 个材料中选择 jj 个材料,使得选择的材料的魔力之和 sumsum 取余数量 ss 的值为 kk 的最大的 sumsum 值。

    转移方程如下:

    $$f_{i,j,k} = \max(f_{i-1,j,k},f_{i-1,j-1,(k+s-a_i\%s)\%s} + a_i)$$

    值得注意的是:max⁡\max 中第二项转移的前提是 fi−1,j−1,(k+s−ai%s)%sf_{i-1,j-1,(k+s-a_i\%s)\%s} 可行,所以初始赋值时要注意。

    最后答案统计就是

    min⁡1≤s≤n(m−fn,s,m%s)/s\min_{1\le s\le n} (m - f_{n,s,m \% s})/s

    时间复杂度 O(n4)O(n^4)。

    • 1

    信息

    ID
    55
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者