acwing 5575. 改变数值

题目

代码及解释

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;const int N=305;
int a[N],b[N];
unordered_map<int,int>f[N];
const int INF=1e9;int gcd(int a,int b){return b ? gcd(b,a%b) : a;
}
int get(unordered_map<int,int>&m,int key){if(m.count(key))return m[key];return INF;
}
// 斐蜀定理
// ax+by=d 对于整数a、b，一定存在整数x、y使得ax+by等于a和b的最小公倍数的倍数
// 这题就是想求是否存在d=1的情况、还有如果存在1，怎么才使得代价最小int main()
{int n;cin>>n;for (int i = 1; i <= n; i ++ ){cin>>a[i];}    for (int i = 1; i <= n; i ++ ){cin>>b[i];}   f[0][0]=0;// 初始化// 寻找最小公约数为1且代价最小的情况// f[i][j]表示前i个数里面当公约数为j时的最小代价和for (int i = 0; i < n; i ++ ){for (auto& [k,v]:f[i]){// 由f[i]去推断f[i+1]。k是公约数，v是这个公约数的代价和// 这一步是由前i个数所有的公约数去得到前i+1个数的每个公约数的代价和（没算上a[i+1]）f[i+1][k]=min(get(f[i+1],k),v); // 这里为什么是取min(f[i+1][k],v)而不是直接用v赋值，// 因为下面算出的公约数d可能与for循环后面的k相等，这样更新时就得与旧值进行比较，取minint d = gcd(a[i+1],k);// 算上a[i+1]的最小公约数f[i+1][d] = min(get(f[i+1],d) , v+b[i+1]);// 算上a[i+1]}}int res = get(f[n],1);if(res==INF)cout<<-1<<endl;else cout<<res<<endl;return 0;
}