首页 > 代码库 > Codeforces_512B: Fox And Jumping
Codeforces_512B: Fox And Jumping
题目链接
题意说的是,有n种卡片,使用第i种卡片可以使当前自己在数轴上的位置移动 l[i],要获得使用第i种卡片的代价是 c[i],求能使自己移动到数轴上任意位置的最小代价,如果不可能则输出-1
当前所拥有的卡片由1->n,逐渐调整map里的值
#include<bits/stdc++.h> using namespace std; const int N=1e5+7; int n; int c[N],l[N]; map<int,int> dp; int gcd(int a,int b) { return b? gcd(b,a%b):a; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&l[i]); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++) { if(dp[l[i]]) dp[l[i]]=min(dp[l[i]],c[i]); else dp[l[i]]=c[i]; for(map<int,int>::iterator it=dp.begin();it!=dp.end();++it) { int t=gcd(it->first,l[i]); if(dp[t]) dp[t]=min(dp[t],it->second+c[i]); else dp[t]=it->second+c[i]; } } printf("%d\n",dp[1]? dp[1]:-1); }
Codeforces_512B: Fox And Jumping
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。