求助一道算法题

[captcha]

输入：
武器初始强度 S
可用强化点数 P

强化规则：
每次可使用 q 个强化点数，使武器强度升为 S * (1 + q / 100)，小数部分舍去
直至强化点数用完

范围：
S, P, q 均为正整数
S <= 10^10
P <= 1000

求强度最高可以升到多少

[captcha]

算了一下 S 超过 10000 的话，好像每次使用 1 点是提升最快的。5000 以下则不确定，例如 4950、167 等很多。

4950 * 1.01 = 4999.5 ----> 4999
4999 * 1.01 = 5048.99 ---> 5048

4950 * 1.02 = 5049，一次用 2 点结果更大

感觉低位只能比较暴力地遍历，不知道有没有好的方法。

[greyqz]

目测可以用动态规划解。

[ballshapesdsd]

难道不是每次用一个强化点数直到用完吗

[maggch]

n 方 dp

[salinapper]

@ballshapesdsd #3

因为有取整这个操作，所以不是..

如果初始是 1，必须一次用 100 点才能变成 2，否则一直是 1。
1 楼也有反例

[chairuosen]

@captcha 你在逗我。。。不管 n 是多大。n*1.01*1.01 和 n*1.02 哪个大？

[ballshapesdsd]

@salinapper #5 审题不细致

[captcha]

@chairuosen
没有逗你，表达式应该是 Math.floor(Math.floor( n * 1.01) * 1.01) 和 Math.floor(n * 1.02)

[aijam]

@captcha q 是固定的值吧？如果 P 不能被 q 整除，剩余的点数怎么处理？

[yzwduck]

这数据范围就暗示着用动态规划欸。
记 M[x] 表示累计使用 x 个强化点数后的最大武器强度，
M[0] = S;
M[x] = upgrade(M[x-i], i), i=0..x。
然后 x 从 0 到 P。