差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:2020暑假精选题目:动态规划 [2020/09/04 09:20]
jjleo ↷ 页面2020-2021:teams:farmer_john:动态规划被移动至2020-2021:teams:farmer_john:2020暑假精选题目:动态规划
+++ 2020-2021:teams:farmer_john:2020暑假精选题目:动态规划 [2020/09/05 13:37] (当前版本)
jjleo [题解]
@@ 行 1: / 行 1: @@
 ======动态规划======
-=====CF802K=====
+=====CF808E=====
+====题意====
+背包，$n$个物品，重量只有$1,2,3$三种。$(n \le 10^5)$
+====题解====
+枚举拿几个重量为$3$的，然后按照性价比给$1,2$的物品进行排序，拿最高的那一些，最后讨论一下进行微调即可（可以证明需要调整的数量不大）。
+=====CF814D=====
 ====题意====
-给定一棵节点数为$n$的树，每一条边有一个权值。现在要求从$1$号点出发，在不经过一个点超过$k$次的情况下经过的边的权值和最大。
+$n$个只有相离和包含关系的圆，覆盖奇数次的区域为阴影，偶数次为空白，选择一些圆将原图分为两部分，每部分分别计算面积，使阴影部分面积最大。$(n \le 1000)$
+====题解====
+第一种做法是贪心，即把覆盖两次的圆取出来，剩下的圆不动。\\
+关于证明，首先通过画图不难看出来，假设第二部分初始是空白的，那么将某个圆移动至第二部分，如果该圆覆盖区域变为阴影，那么总面积一定是增加或不变的，反之会减少或不变。\\
+同理，可以把圆转换为任意形状的闭合区域。\\
+当把覆盖两次的圆移动至左侧后，对于两次以上的圆，无论怎么移动，第二部分出现空白，总面积$\leq$最优面积。\\
+如果移动覆盖一次的圆，实际上就是相当于把覆盖两次及以上的圆移动到第二部分，肯定是不优的。 \\
+第二种做法是dp。画图可以发现圆的关系构成一棵树，可以通过$O(n^2)$寻找包含自己最小的圆作为父亲来建树。再观察可以发现题目本质上是要将这棵树的每个节点划分到两棵树上（类似虚树），其中每棵虚树上，奇数深度的点贡献为正，偶数深度的点贡献为负，因此直接dp即可。设$f_{i,0/1,0/1}$为以$i$为根节点的子树中，该节点作为第一/二棵树奇/偶数深度深度的节点时的权值最大值，转移时注意细节即可。
+=====CF868F=====
+====题意====
+给定一个序列 $a$ ，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。$k \le \min(n, 20), n \le 10^5, 1 \le a_i \le n$
 ====题解====
-设$f_{i,0/1}$为以$i$为根的子树中进去后回溯/不回溯的边权最大值，合并时将子树对应值排序即可，如果回溯的话只能从回溯的值里选，如果不回溯的话只能选一个不回溯的子树其它都要回溯，最后答案为$f_{1,1}$。
+令 $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)$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具