裴蜀定理+Dp
比较有意思的一道题，给了很多的选择来乱搞。
Solution
比较暴力的一种做法，可能之后还回来补充。
首先有一个比较显然的结论，我们必须要凑出每次向右移动1的方案，否则不可能有解，这时回过头来再考虑裴蜀定理，有$ax+by=gcd(a,b)$，且其中数的个数可拓展到$n$，那么显然如果我们选出来的数的$gcd$等于一即可。
此时来设计$Dp$方程，不难发现有种暴力转移的$Dp$是：
$$
f_{gcd(l[i],x)}= \min f_x+c[i]
$$
最后的$f_1$就是答案，复杂度是$O(n\sum l_i)$的。
考虑优化，其实就是需要去除无关状态，我们用$map$来转移，它会自动帮我们只保留有用状态的。
后半部分的状态也可以用状压来写，复杂度$O(n^22^9)$，比这个要优秀。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 305;
int n, m;
int l[N], c[N];
map<int, int> mp;
inline int gcd(int x, int y)
{
if(!y) return x;
return y ? gcd(y, x % y) : x;
}
int main()
{
read(n);
for(int i = 1;i <= n;i ++) read(l[i]);
for(int i = 1;i <= n;i ++) read(c[i]);
for(int i = 1, Gcd;i <= n;i ++)
{
for(PII j : mp)
{
Gcd = gcd(l[i], j.first);
if(mp[Gcd] == 0) mp[Gcd] = j.second + c[i];
else mp[Gcd] = min(mp[Gcd], j.second + c[i]);
}
if(mp[l[i]] == 0) mp[l[i]] = c[i];
else mp[l[i]] = min(mp[l[i]], c[i]);
}
if(!mp[1]) puts("-1");
else write(mp[1]);
return 0;
}
|