2020-2021:teams:farmer_john:2020暑假精选题目:动态规划
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:动态规划 [2020/09/05 13:29] jjleo [题解] |
2020-2021:teams:farmer_john:2020暑假精选题目:动态规划 [2020/09/05 13:37] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 30: | 行 30: | ||
| ====题解==== | ====题解==== | ||
| 设$f_{i,j,k}$为最终序列中有$i$个数，序列中数的选择状态为$j$，最后一个数的原位置下标为$k$时最终序列最后一个值的最小值。 | 设$f_{i,j,k}$为最终序列中有$i$个数，序列中数的选择状态为$j$，最后一个数的原位置下标为$k$时最终序列最后一个值的最小值。 | ||
| + | |||
| + | 首先$O(2^n)$预处理出所有子集对应元素的权值和。转移时枚举当前状态的补集的子集，要求该子集的和大于当前末尾元素的值，且子集中至少存在一个在当前元素位置右侧的元素，将其中满足条件下标最靠左的作为新的位置（显然这样是更优的）。转移时记录怎么转移来的，便于最后输出答案。时间复杂度$O(n^23^n)$。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/动态规划.1599283780.txt.gz · 最后更改: 2020/09/05 13:29 由 jjleo
