当前位置:首页 > 动态规划 > 背包 > 正文
洛谷P6189跑步(NOIOnline第一场入门组B)
1491+

题目大意:n米路,拆分成$a_1, a_2, a_3…$,要求序列a不递增,有多少种方案?

题目描述

小 H 是一个热爱运动的孩子,某天他想给自己制定一个跑步计划。小 H 计划跑 $n$ 米,其中第 $i(i \geq 1)$ 分钟要跑 $x_i$ 米($x_i$ 是正整数),但没有确定好总时长。

由于随着跑步时间增加,小 H 会越来越累,所以小 H 的计划必须满足对于任意 $i(i >1)$ 都满足 $x_i \leq x_{i-1}$。

现在小 H 想知道一共有多少个不同的满足条件的计划,请你帮助他。两个计划不同当且仅当跑步的总时长不同,或者存在一个 $i$,使得两个计划中 $x_i$ 不相同。

由于最后的答案可能很大,你只需要求出答案对 $p$ 取模的结果。

输入输出格式

输入格式

输入只有一行两个整数,代表总米数 $n$ 和模数 $p$。

输出格式

输出一行一个整数,代表答案对 $p$ 取模的结果。

输入输出样例

输入样例 #1

4 44

输出样例 #1

5

输入样例 #2

66 666666

输出样例 #2

323522

输入样例 #3

66666 66666666

输出样例 #3

45183149

说明

样例输入输出 1 解释

五个不同的计划分别是:$\{1,1,1,1\}$,$\{2,1,1\}$,$\{3,1\}$,$\{2,2\}$,$\{4\}$。

数据规模与约定

本题共 $10$ 个测试点,各测试点信息如下表。

| 测试点编号 | $n \leq$ | 测试点编号 | $n \leq$ |
| :———-: | :———: | :———-: | :———: |
| $1$ | $5$ | $6$ | $2\times 10^3$ |
| $2$ | $10$ | $7$ | $5\times 10^3$ |
| $3$ | $50$ | $8$ | $2\times 10^4$ |
| $4$ | $100$ | $9$ | $5\times 10^4$ |
| $5$ | $500$ | $10$ | $10^5$|

对于全部的测试点,保证 $1 \leq n \leq 10^5$,$1 \leq p < 2^{30}$。

解题思路

爆搜30,记忆化50,数学方法70,分块优化100。

程序实现

首先是暴力搜索,跟自然数拆分是同样的做法,不仅可以从大到小搜,还可以从小到大搜,方案数是一样的。

时间复杂度是组合数的复杂度,至少可得20分,实测30分。

其次是加入记忆化,第k段路,前一段跑p米,还剩下s米,那么后面的情况(剩下s米,这次至少跑p米)是完全一样的,可以加入记忆化,避免重复调用自己。

时间复杂度:O(n*n*n),可得50分。

改变搜索对象,由搜索每一段路的距离,变成每一种长度的路有多少段!

因为代码第9行的循环,是每次加k的,所以时间复杂度跟筛法、调和级数有关:$O(n*n*log_2n)$,可得60分。

突然发现这是递推的模板?相当于n个相同的苹果,放入n个相同的盘子的方案数!n米路,每一米看成一个苹果;分到n段时间,每1分钟看成一个盘子!

递推:f[i][j]表示i个苹果放入j个盘子,要么全部盘子不空,由f[i-j][j]转移过来;要么至少一个盘子为空,由f[i][j-1]转移过来,所以f[i][j] = f[i-j][j] + f[i][j-1]。

时间复杂度:O(n*n),可得70分。

完全背包问题:每一种长度看成一个物品,可以选无限个,现在需要将n米装满!

时间复杂度:O(n*n),可得70分。

分块优化:因为n*n超时,所以需要优化。容量是很难变小的,但是物品则可以分类:小于$\sqrt{n}$和大于$\sqrt{n}$的。

对于小于的部分,我们可以跑完全背包。

对于大于的部分,我们可以再写个DP:g[i][j]表示长度为i,有j个大于等于m=$\sqrt{n}$的物品。转移也是分成两类:j个都是大于m和j个中至少1个不大于m。若j个都大于m,那么可以每一个减去1,还是有j个大于等于m(f[i-j][j]);若至少一个等于m,那么由j-1个新增1个m转移过来(f[i-m][j-1])。跟“放苹果”有点相似。

时间复杂度:$O(n\sqrt{n})$,可得满分。

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P6189跑步(NOIOnline第一场入门组B):等您坐沙发呢!

发表评论

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