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 $ 有关系

#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;
}