动态规划,$O(x\sqrt x)$
首先,当两种植物的全部法力都耗光时,游戏就会结束,因此 $h$ 满足 $\sum_{i = 1}^{h} \le x + y$。其次,可以证明 $h$ 确实是满足该不等式的最大整数。
先证明 $[1, \frac{h(h + 1)}{2}]$ 中的任何一个整数,都可以从 $1, 2, \cdots, h$ 挑选若干个数求和得到(每个数只使用一次)。
归纳法:
- 当 $h = 1$ 时,$\frac{h(h + 1)}{2} = 1$,而 $1 = 1$,满足条件。
- 假设 $h = k \ge 2$ 时,$[1, \frac{k(k + 1)}{2}]$ 中的任何一个整数,都可以从 $1, 2, \cdots, k$ 挑选若干个数求和得到(每个数只使用一次)。当 $h = k + 1$ 时,如下图所示,由于 $[\frac{k(k + 1)}{2} + 1, \frac{(k + 1)(k + 2)}{2}]$ 长度为 $k + 1$,只要从 $\frac{k(k + 1)}{2}$ 往左数 $k + 1$ 个数(由假设,得到它们不需要使用 $k + 1$),让它们每个都加上 $k + 1$,就能凑出 $[\frac{k(k + 1)}{2} + 1, \frac{(k + 1)(k + 2)}{2}]$ 中的所有数,因此当 $h = k + 1$ 时,结论也成立。补充:当 $k \ge 2$ 时,$\frac{k(k + 1)}{2} \ge \frac{2(k + 1)}{2} = k + 1$。
| k+1 | k+1 |
|----------|---------|---------|---------
1 k(k+1)/2 (k+1)(k+2)/2
由此得证。
因此,当 $h$ 取到上界时,若 $x \le \frac{h(h + 1)}{2}$,只需从 $1, 2, \cdots h$ 中选若干个僵尸给植物一,剩余的给植物二($x$ 可以被凑出,且剩余数之和 $\frac{h(h + 1)}{2} - x \le y$)。若 $x > \frac{h(h + 1)}{2}$,则可将所有僵尸都给植物一。
用 $f(v)$ 表示分 $v$ 的法力给植物一,一共有多少种分法。把僵尸看成物品,每种物品只能选一次,第 $i$ 个物品的体积为 $i$,等价于求装满容量为 $v$ 的背包有多少种选法。
当植物一获得的物品确定后,植物二获得的物品也是确定的,由乘法原理,将物品分给两种植物的方案数等于分给植物一的方案数。假设植物一分到的法力为 $t$,则 $\frac{h(h + 1)}{2} - y \le t \le x$,因此答案为 $\sum_{i = \frac{h(h + 1)}{2} - y}^{x} f(i)$。
rv = lambda dt: dt(input())
rl = lambda dt: [dt(x) for x in input().split()]
x, y = rl(int)
MOD = int(1e9) + 7
s = lambda n: n * (n + 1) // 2
h = 0
while s(h + 1) <= x + y:
h += 1
f = [0] * (x + 1)
f[0] = 1
for i in range(1, h + 1):
for j in range(x, i - 1, -1):
f[j] = (f[j] + f[j - i]) % MOD
print(sum(f[max(0, s(h) - y):x + 1]) % MOD)
为什么你那么厉害啊啊啊啊啊啊啊啊
我这是转述y总视频,真正厉害的人在周赛排行榜里。
猪脑过载了,请问一下,y为什么要大于等于h * (h + 1) / 2 - x了?为什么求解的h是(h + 2) * (h + 1) / 2 公式计算,而不是h * (h + 1) / 2来计算
第一个问题:生存 h 关,需要消耗的法力是 h * (h + 1) / 2,分出 x 给植物一,剩余的法力必须全部给植物二,所以植物二的法力必须充足,即 y >= h * (h + 1) / 2 - x。
第二个问题:如果用 h * (h + 1) / 2 计算,while 退出后,h * (h + 1) / 2 > x + y,超过了植物的法力上限,不满足要求。
第二个问题理解了,本质是找到最大的h,满足h * (h + 1) / 2 <= (x + y)。第一个问题还是不懂,不理解植物二的充足的含义
对。倒数第三段是分类讨论,用来说明当 h 取到满足 h * (h + 1) / 2 <= (x + y) 的最大整数时,至少存在一种分配方案,能够让玩家生存 h 关。情况一:如果 x > h * (h + 1) / 2,那么对 y 没有任何要求,因为只用植物一就能生存 h 关。情况二:如果 x <= h * (h + 1) / 2,则存在一种分配方法,可以使得刚好用光植物一的法力 x,因为 x 一定能通过 1,2,…,h 凑出。此时剩余的关卡需要的总法力值是 h * (h + 1) / 2 - x,由于 h * (h + 1) / 2 <= (x + y),所以 h * (h + 1) / 2 - x <= y,因此植物二的法力值足够生存剩余的关卡,注意剩余关卡不一定连续,只是被植物一选完后的其它关卡。综上,无论哪种情况,玩家都可以生存 h 关。
理解啦,谢谢。但是下次遇到类似的,不一定能分析的出来。。。