当前位置:首页 > 搜索 > 记忆化搜索 > 正文
GDKOI2021普及组Day3D好序列
1038+

题目大意:n个格子,填入0~n,要求前i个的和不小于后i个的和,有多少种填法?

解题思路

暴力填格子,每次填入0~n,最后验证即可过样例!当然,我们也可以直接剪枝,每次填2个格子,填完统计前缀和、后缀和,如果发现前缀和小,剪枝!

改成倒搜后,加入记忆化,即可获得30分!

发现状态太大,降维处理,前缀和、后缀和,我们只关注他们的差,且差不为负数,故可以降一维数组。

不想再优化的话,打表2min即可。再优化就只能多记忆一下,因为现在记忆的是填前缀,没记填后缀。

我们只需要改回一个一个格子填,即可多记忆一半的内容!

程序实现

GDKOI2021普及组Day3D好序列:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!