这是一个创建于 2097 天前的主题，其中的信息可能已经有所发展或是发生改变。
输入：
武器初始强度 S
可用强化点数 P
强化规则：
每次可使用 q 个强化点数，使武器强度升为 S * (1 + q / 100)，小数部分舍去
直至强化点数用完
范围：
S, P, q 均为正整数
S <= 10^10
P <= 1000
求强度最高可以升到多少
武器初始强度 S
可用强化点数 P
强化规则：
每次可使用 q 个强化点数，使武器强度升为 S * (1 + q / 100)，小数部分舍去
直至强化点数用完
范围：
S, P, q 均为正整数
S <= 10^10
P <= 1000
求强度最高可以升到多少
 |
1
captcha OP 算了一下 S 超过 10000 的话，好像每次使用 1 点是提升最快的。5000 以下则不确定，例如 4950、167 等很多。
4950 * 1.01 = 4999.5 ----> 4999 4999 * 1.01 = 5048.99 ---> 5048 4950 * 1.02 = 5049，一次用 2 点结果更大 感觉低位只能比较暴力地遍历，不知道有没有好的方法。 |
 |
2
greyqz 2019-02-26 18:09:03 +08:00 via Android
目测可以用动态规划解。
|
 |
3
ballshapesdsd 2019-02-26 18:13:57 +08:00
难道不是每次用一个强化点数直到用完吗
|
 |
4
maggch 2019-02-26 18:15:28 +08:00 via Android
n 方 dp
|
 |
5
salinapper 2019-02-26 18:16:51 +08:00
|
 |
6
chairuosen 2019-02-26 18:17:56 +08:00
@captcha 你在逗我。。。不管 n 是多大。n*1.01*1.01 和 n*1.02 哪个大？
|
|
7
ballshapesdsd 2019-02-26 18:22:56 +08:00
@salinapper #5 审题不细致
 |
|
8
captcha OP @chairuosen
没有逗你，表达式应该是 Math.floor(Math.floor( n * 1.01) * 1.01) 和 Math.floor(n * 1.02) |
 |
10
yzwduck 2019-02-26 20:06:40 +08:00
这数据范围就暗示着用动态规划欸。
记 M[x] 表示累计使用 x 个强化点数后的最大武器强度， M[0] = S; M[x] = upgrade(M[x-i], i), i=0..x。 然后 x 从 0 到 P。 |
Select Language