2020-2021:teams:farmer_john:2020暑假精选题目:动态规划
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:动态规划 [2020/09/04 13:33] 2sozx |
2020-2021:teams:farmer_john:2020暑假精选题目:动态规划 [2020/09/05 13:37] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| 01背包，$n$个物品，重量只有$1,2,3$三种。$(n \le 10^5)$ | 01背包，$n$个物品，重量只有$1,2,3$三种。$(n \le 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| - | 枚举拿几个重量为$3$的，然后按照性价比给$1,2$的物品进行排序，拿最高的那一些，最后讨论一下进行微调即可（可以证明需要调整的数量不打）。 | + | 枚举拿几个重量为$3$的，然后按照性价比给$1,2$的物品进行排序，拿最高的那一些，最后讨论一下进行微调即可（可以证明需要调整的数量不大）。 |
| 行 21: | 行 21: | ||
| =====CF868F===== | =====CF868F===== | ||
| ====题意==== | ====题意==== | ||
| - | 01背包，$n$个物品，重量只有$1,2,3$三种。$(n \le 10^5)$ | + | 给定一个序列 $a$ ，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。$k \le \min(n, 20), n \le 10^5, 1 \le a_i \le n$ |
| ====题解==== | ====题解==== | ||
| - | 枚举拿几个重量为$3$的，然后按照性价比给$1,2$的物品进行排序，拿最高的那一些，最后讨论一下进行微调即可（可以证明需要调整的数量不打）。 | + | 令 $dp_{i,j}$ 表示 $1 \sim i$ 分 $j$ 段的最小花费。从题目中很容易看出 $dp$ 的转移方程，$dp_{i,j} = \min(dp_{k,j - 1} + w_{k + 1, i})$ ，其中 $w_{i, j}$ 为 $i \sim j$ 的花费。容易发现状态转移的决策点是单调的，并且每一层的 $dp$ 均是由上一层转移过来，因此可以通过分治 $dp$ 来解决问题。$w_{i,j}$ 的计算可以通过类似莫队的方式进行更改，总体复杂度是 $O(nk\log(n))$。 |
| + | =====CF1342F===== | ||
| + | ====题意==== | ||
| + | 给定一个长度为$n$的序列，每次操作可以选择任意两个元素，删除其中一个，将它的值加到另一个上面，问最少多少次操作可以将序列变为严格单增。$(1 \le n \le 15)$ | ||
| + | ====题解==== | ||
| + | 设$f_{i,j,k}$为最终序列中有$i$个数，序列中数的选择状态为$j$，最后一个数的原位置下标为$k$时最终序列最后一个值的最小值。 | ||
| + | |||
| + | 首先$O(2^n)$预处理出所有子集对应元素的权值和。转移时枚举当前状态的补集的子集，要求该子集的和大于当前末尾元素的值，且子集中至少存在一个在当前元素位置右侧的元素，将其中满足条件下标最靠左的作为新的位置（显然这样是更优的）。转移时记录怎么转移来的，便于最后输出答案。时间复杂度$O(n^23^n)$。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/动态规划.1599197621.txt.gz · 最后更改: 2020/09/04 13:33 由 2sozx
