1 条题解
-
0
题目分析
- 考点:DP,贪心。
- 难度:CSP-J T3+
测试点 1~4
留给暴力搜索的部分。
时间复杂度为 。
测试点 5~10
留给暴力DP的部分。
设 考虑了 家店,选了 个家电, 个家具, 个装饰的最小费用。
有转移:
$$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)$$最后答案就是
复杂度为 。
测试点 11~14
同样可以 DP。
但也有贪心做法。
我们按 给店铺排序,前 家点选购家具,后 家点选购家电。
为什么?因为若 ,则 。
测试点 15~20
我们可以把上面的贪心做法和dp做法结合起来。
设 表示虑了 家店,选了 个装饰的最小费用,那么剩下的 个物品就会按贪心的想法优先选择购买家具,然后购买家电。
按 给店铺排序,那么就有转移:
$$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}$$时间复杂度是
- 1
信息
- ID
- 50
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者