2019 ECNU XCPC March Selection 4

ECNU XCPC March Selection #4

可能是 dp 专场了。

推荐资料

dp 没啥好推荐的资料。

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

Problem A

了解一下补题的重要性？

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

要是补题还是不明显，以后可能还会这么搞。

[题解]

Problem C

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

可以 dp ，状态为：

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

搜索也是可以的：

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

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

Problem D

经典大背包问题。

折半搜索。

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

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

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