2019 ECNU XCPC March Selection 4

ECNU XCPC March Selection #4

可能是 dp 专场了。

推荐资料

dp 没啥好推荐的资料。

打开 codeforces ，搜索 tag 为 dp 的，刷题。

Problem A

了解一下补题的重要性？

显然补题不只有这个作用。

要是补题还是不明显，以后可能还会这么搞。（我出我自己）

[题解]

Problem B

显然贪心。

排序以后插入堆。

最小的必须放在当前结点，无法选择。

要使得字典序最大，大的一半给左节点，小的一半给右节点。

Problem C

经典盒子装球问题中的一种。

可以 dp ，状态为：

$f[i][j]$ 表示 $i$ 个球放入 $j$ 个盒子的方案数。

搜索也是可以的：

$dfs(n,k,x)$ 表示将 $n$ 分成 $k$ 份,最小的一份 $\ge x$ 的方案数。

显然答案是 $dfs(m,n,0)$ 。记忆化搜索一下。

Problem D

经典大背包问题。

折半搜索。

考虑枚举 $20$ 个物品的时候的情况。

也就是把 $40$ 个物品分成两半枚举出所有情况，针对其中的一边，二分最优解的位置。

题解过于见解看不懂的。出门左转[大背包问题分析]

Problem E

感觉也是比较基本的 dp 。

看到数都不是很大，于是我们考虑从这点入手设计状态。

$f[i][j]$ 表示从第 $i$ 位开始，消成 $j$ 所需要的位置数量（显然，一定是连续的一段）。

考虑状态转移，如果 $f[i][j-1]>0$ 而且 $f[i+f[i][j-1]][j-1]>0$ ，也就是出现了两段消完以后连续的两个数一样，那么可以继续消，也就是 $f[i][j]=f[i+f[i][j-1]][j-1]+f[i][j-1]$ 。

Problem F

因为是最小的代价，所以到最后的序列中的每个数字肯定在原先的序列中出现过。

我们用一个 $c$ 数组拷贝原先的 $a$ 数组，然后进行从小到大排序。

那么之后我们考虑 dp ，因为是 $5000$ 的数据，考虑 $O(n^2)$ 做法。设 $dp[i][j]$ 表示前 $i$ 个已经符合要求，而且最大数不大于原序列第 $j$ 个元素最小需要的代价。

那么我们可以得出转移方程 $dp[i][j]=min(dp[i][j−1],dp[i−1][j]+abs(a[i]−c[j])$ 。