当前位置:首页 > 递推 > 正文
洛谷P1806跑步[NOI导刊]
937+

题目大意:将n进行自然数拆分,要求每个位置数字不一样,共有多少种方案?

题目描述

路人甲准备跑 $n$ 圈来锻炼自己的身体,他准备分多次($\gt1$)跑完,每次都跑正整数圈,然后休息下再继续跑。

为了有效地提高自己的体能,他决定每次跑的圈数都必须比上次跑的多。

可以假设他刚开始跑了 $0$ 圈,那么请问他可以有多少种跑完这 $n$ 圈的方案?

输入输出格式

输入格式

一行一个整数,代表 $n$。

输出格式

一个整数表示跑完这 $n$ 圈的方案数。

输入输出样例

输入样例 #1

212

输出样例 #1

995645335

说明

对于 $100\%$ 的数据,保证 $5\le n\le 500$。

解题思路

暴力记忆化:若干个格子,上一个格子填的是p-1,还剩下s没拆分,那么这个格子填p~s,填完得到1种方案,记忆化可通过。

递推方案:f[i][j]表示跑i圈,最后一次为j圈的方案数,那么之前的状态是跑了i-j圈,最后一次可以是1~j-1圈,当然也必须不超过i-j。

程序实现

爆搜,时间复杂度$O(n^3)$

递推,不判断k是否超过i-j也行,因为默认为0,时间复杂度$O(n^3)$

前缀和优化:s[i][j]表示跑i圈,最后一圈不超过j的方案数。

降维优化,依次算出跑n圈,最后一圈是1、2、3、……n的方案数,累计起来。

洛谷P1806跑步[NOI导刊]:等您坐沙发呢!

发表评论

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