1 条题解

  • 0
    @ 2026-11-15 13:13:21

    题目分析

    • 考点:DP,贪心。
    • 难度:CSP-J T3+

    测试点 1~4

    留给暴力搜索的部分。

    时间复杂度为 O(3n)O(3^n) 。

    测试点 5~10

    留给暴力DP的部分。

    设 fi,j,kf_{i,j,k} 考虑了 1∼i1\sim i 家店,选了 jj 个家电, kk 个家具,i−j−ki-j-k 个装饰的最小费用。

    有转移:

    $$f_{i,j,k}=\min(f_{i-1,j-1,k}+a_i,f_{i-1,j,k-1}+b_i,f_{i-1,j,k}+c_i)$$

    最后答案就是 fn,a,bf_{n,a,b}

    复杂度为 O(n3)O(n^3) 。

    测试点 11~14

    同样可以 n2n^2 DP。

    但也有贪心做法。

    我们按 bi−aib_i-a_i 给店铺排序,前 bb 家点选购家具,后 aa 家点选购家电。

    为什么?因为若 b1−a1<b2−a2b_1-a_1<b_2-a_2,则 b1+a2<b2+a1b_1+a_2<b_2+a_1。

    测试点 15~20

    我们可以把上面的贪心做法和dp做法结合起来。

    设 fi,jf_{i,j} 表示虑了 1∼i1\sim i 家店,选了 jj 个装饰的最小费用,那么剩下的 i−ji-j 个物品就会按贪心的想法优先选择购买家具,然后购买家电。

    按 bi−aib_i-a_i 给店铺排序,那么就有转移:

    $$f_{i,j}=\begin{cases} \min(f_{i-1,j-1}+c_i,f_{i-1,j}+b_i&(i-j\le B)\\ \min(f_{i-1,j-1}+c_i,f_{i-1,j}+a_i&(i-j> B) \end{cases}$$

    时间复杂度是 O(n2)O(n^2)

    • 1

    信息

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