给定n个跳跃卡片,卡片中有距离和相应的代价,初始的位置为0,问至少需要多少代价可以跳至任意的位置.
如跳跃10距离的代价为1,那么花费1的代价可以跳至10倍数的任意地方.
要跳至任意距离很容易就想到将所有的卡片组合成能跳跃1距离的"大卡片"
两张卡片能组合成的"大卡片"跳跃距离最小是这两张卡片的最大公约数
对前1至前n张卡片进行遍历,求出能组合成‘新距离‘的最小代价
状态转移方程 dp[k]=min(dp[k],dp[j]+cost[i]) 其中k=gcd(j,i)
#include <iostream>
using namespace std;
#include <map>
int gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
map<int,int> dp;
int n;
int cost[500];
int lenth[500];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>lenth[i];
}
for(int i=1;i<=n;i++)
{
cin>>cost[i];
}
dp[0]=0;
for(int i=1;i<=n;i++)
{
map<int,int>::iterator it=dp.begin();
for(;it!=dp.end();it++)
{
int t=gcd(lenth[i],it->first);
if(dp.count(t))
{
dp[t]=min(dp[t],cost[i]+it->second);
}
else
{
dp[t]=cost[i]+it->second;
}
}
}
if(dp.count(1))
cout<<dp[1]<<endl;
else
cout<<"-1"<<endl;
return 0;
}
原文：http://www.cnblogs.com/wzsblogs/p/4286890.html