Codeforces 510D(DP+GCD)

Codeforces 510D
题意:给出$n$张卡上有数字$l_i$,每张卡可以用无限次,每种卡需要$c_i$的花费,问最少用多少花费,能够组成所有的自然数。

能组成所有的数字则这些选的数字$gcd$为1。CF 1011E可以由拼数想到gcd,那么这题也一样。显然得出以上的结论。
那么这样的话,我们只需要用最少的钱找出几个数$gcd=1$即可。我们可以设$dp(i)$为$gcd=i$时最小花费,初始值为$dp(0)=0$,因为$0$与任何数$gcd$等于任何数。不能将所有$l_i$直接加进来,考虑重复的$l_i$。转移方程即为$dp(i)=dp(j)+c_x$,并且能有一个数$x$使得$gcd=j$可以转移到$gcd=i$。
但是数据很大开不了数组啊,由于总数小,就可以用map。

知识点:
超限但是总数小:vector->二维数组压第二维,map->一维数组压第一维
拼数问题和 $ gcd $ 有关系

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
pair<int, int > cd[305];
map<int, int > dp;
int n;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &cd[i].first);
for (int i = 1; i <= n; i++) scanf("%d", &cd[i].second);
dp[0] = 0; //l[i] 可能重复不能全部直接 dp[cd[i].first] = cd[i].second 会把最优解换掉
for (int i = 1; i <= n; i++) {
int &x = cd[i].first, &c = cd[i].second;
for (map<int, int >::iterator it = dp.begin(); it != dp.end(); it++) {
int y = it->first;
int g = gcd(x, y);
if (dp.find(g) == dp.end()) dp[g] = dp[y] + c;
else if (dp[g] > dp[y] + c) dp[g] = dp[y] + c;
}
}
if (dp.find(1) != dp.end()) printf("%d\n", dp[1]); else printf("%d\n", -1);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
------ 本文结束 ------