Difference between revisions of "2019 ECNU XCPC March Selection 4"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 39: | Line 39: | ||
== Problem D == | == Problem D == | ||
| + | 经典大背包问题。 | ||
| + | 折半搜索。 | ||
| + | |||
| + | 考虑枚举 $20$ 个物品的时候的情况。 | ||
| + | |||
| + | 也就是把 $40$ 个物品分成两半枚举出所有情况，针对其中的一边，二分最优解的位置。 | ||
| + | |||
| + | 题解过于见解看不懂的。出门左转[[https://blog.csdn.net/qq_40679299/article/details/82181524 大背包问题分析]] | ||
== Problem E == | == Problem E == | ||
Revision as of 13:41, 28 March 2019
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$ 个物品分成两半枚举出所有情况，针对其中的一边，二分最优解的位置。
题解过于见解看不懂的。出门左转[大背包问题分析]