首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

求助一道算法题

  •  
  •   captcha · 52 天前 · 588 次点击
    这是一个创建于 52 天前的主题,其中的信息可能已经有所发展或是发生改变。
    输入:
    武器初始强度 S
    可用强化点数 P

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

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

    求强度最高可以升到多少
    10 回复  |  直到 2019-02-26 20:06:40 +08:00
        1
    captcha   52 天前
    算了一下 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   52 天前 via Android
    目测可以用动态规划解。
        3
    ballshapesdsd   52 天前
    难道不是每次用一个强化点数直到用完吗
        4
    maggch   52 天前 via Android
    n 方 dp
        5
    salinapper   52 天前
    @ballshapesdsd #3

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

    如果初始是 1,必须一次用 100 点才能变成 2,否则一直是 1。
    1 楼也有反例
        6
    chairuosen   52 天前
    @captcha 你在逗我。。。不管 n 是多大。n*1.01*1.01 和 n*1.02 哪个大?
        7
    ballshapesdsd   52 天前
    @salinapper #5 审题不细致
        8
    captcha   52 天前
    @chairuosen
    没有逗你,表达式应该是 Math.floor(Math.floor( n * 1.01) * 1.01) 和 Math.floor(n * 1.02)
        9
    aijam   52 天前
    @captcha q 是固定的值吧?如果 P 不能被 q 整除,剩余的点数怎么处理?
        10
    yzwduck   52 天前
    这数据范围就暗示着用动态规划欸。
    记 M[x] 表示累计使用 x 个强化点数后的最大武器强度,
    M[0] = S;
    M[x] = upgrade(M[x-i], i), i=0..x。
    然后 x 从 0 到 P。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2295 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 12:57 · PVG 20:57 · LAX 05:57 · JFK 08:57
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1