首页 > 代码库 > Codeforces Round #290 Div1 B
Codeforces Round #290 Div1 B
Codeforces Round #290 Div1 B
Problem
有一只青蛙在x轴上跳，起初在原点，现有N种跳跃技能可以购买，每技能有两属性：跳跃长度Li 以及 花费Ci。若购买了第 i 种技能，则可以从 y 位置跳跃到 y+Li 或者 y-Li 位置，但需花费Ci 元。求最小花费使得青蛙可以跳到每一个整数点上，若无法做到，输出－1。
Limits
Time Limit(ms): 2000
Memory Limit(MB): 256
N: 300
Li: [1, 10^9]
Ci: [1, 10^5]
Solution
若购买了n个属性使得青蛙可以跳到每个整数点上，则这n个属性的跳跃长度Li的最大公约数一定为1，或者说n个数互素。用dp方法即可解决，需在map上dp。
More
设dp[i]表示 最大公约数为 i 时的最小花费为dp[i]。则转移方程自然为：dp[gcd(i, L)]=min(dp[gcd(i, L)]，dp[i]+C)；但需在map上dp，最好再额外开个map来做临时存储。
由于gcd的性质，可以证明状态数很小，不会超时。
Complexity
Time Complexity: Very Small
Memory Complexity: Very Small
Source
Codeforces Round #290 Div1 B
Code
Codeforces Round #290 Div1 B From My Github
Codeforces Round #290 Div1 B
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。