Luogu Link

洛谷题解满了于是就来这里写了

大致题意

给出 $n$ 张卡片，分别有 $l_i$ 和 $c_i$。在一条无限长的纸带上，你可以选择花 $c_i$ 的钱来购买卡片 $i$，从此以后可以向左或向右跳 $l_i$ 个单位。问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 $-1$。

题解

分析该问题，发现想要跳到每一个格子上，必须使得所选数 $l_{i_1},\dots ,l_{i_k}$ 通过数次相加或相减得出的绝对值为 $1$，也即存在整数 $x_1,\dots ,x_n$ 使得 $l_{i_1}{x}_1+\cdots +l_{i_k}{x}_k=1$。由多个整数的裴蜀定理逆定理，这相当于 从数组 $l_1,\dots ,l_n$ 选择若干个数，满足它们的最大公因数为 $1$，同时要求代价和最小。

注：（给不熟悉裴蜀定理的人）

裴蜀定理：设 $a,b$ 是不全为零的整数，则存在整数 $x,y$, 使得 $ax+by=gcd(a,b)$.

多个整数裴蜀定理：设 $a_1,a_2,\dots ,a_n$ 是不全为零的整数，则存在整数 $x_1,x_2,\dots ,x_n$, 使得 $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=gcd(a_1,a_2,\dots ,a_n)$。其逆定理也成立：设 $a_1,a_2,\dots ,a_n$ 是不全为零的整数，$d>0$ 是 $a_1,a_2,\dots ,a_n$ 的公因数，若存在整数 $x_1,x_2,\dots ,x_n$, 使得 $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=d$，则 $d=gcd(a_1,a_2,\dots ,a_n)$。

好了，现在问题已经转化成了一个动态规划问题。如果看了刚才的定理有点忘了的话，那就再把这个问题重申一遍：

从数组 $l_1,\dots ,l_n$ 选择若干个数，满足它们的最大公因数为 $1$，同时要求代价和 $\sum _{l_i}^{}{c}_i$ 最小。（$l_i$ 是被选中的）

仔细一看——这是不是有点像 0-1 背包？

让我们来回顾一下普通的 0-1 背包求的是什么：在 $(\sum _{}^{}{w}_i)<W$ 时，$max(\sum _{}^{}{v}_i)$。（$i$ 是被选中的）

而对于这个问题，只不过是把价值改成了代价，又改了改限制条件而已

我们设 $f_{i,j}$ 表示考虑前 $i$ 个数且 最大公因数为 $j$ 的 最小代价（注意与普通 0-1 背包对比，后者是设 $f_{i,j}$ 表示考虑前 $i$ 个数且 和为 $j$ 的 最大价值），则有转移方程：

$f_{i,j}=\underset{gcd(k,l_i)=j}{min}{f}_{i-1,k}+c_i.$

（请自行对比普通 0-1 背包转移方程以获得更深的理解）

DP 后最终的总代价即为 $f_{n,1}$。

然而这样的复杂度是 $O(n\sum _{}^{}{a}_i)$，会 TLE。

考虑一个简单的优化：即消去无用状态。

我们只需要开个 map，每次把访问过的 $x$ 执行转移即可，这样就能轻松过题了。

事实上，这题用 unordered_map 应该更优，比较这题只需建立映射关系就行，不需要 map 那样的自动有序特性。

如果不想用 map 之类的 STL ，那么也可以如同一般的 0-1 背包问题，可以用滚动数组优化，去掉第一维。总之优化方法非常多，也都比较简单。

因此，这就是裴蜀定理+01背包+gcd=紫题

代码（可能有点抽象）

#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,l[N],c[N];
map<int,int> pre;
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]);
    pre[l[1]]=c[1];
    for(int i=2;i<=n;i++)
    {
        for(auto k:pre) pre[__gcd(k.first,l[i])]==0?pre[__gcd(k.first,l[i])]=k.second+c[i]:pre[__gcd(k.first,l[i])]=min(pre[__gcd(k.first,l[i])],k.second+c[i]);
        pre[l[i]]=min((pre[l[i]]==0)?INT_MAX:pre[l[i]],c[i]);
    }
    printf("%d",pre[1]==0?-1:pre[1]);
}

十八行切掉的水紫