题目链接：https://ac.nowcoder.com/acm/contest/940/E/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。
她想知道，最终所有取出的数的和的最小值是多少？
注：若a%k==0，则称k是a的因子。若一个数有且仅有两个因子，则称其是素数。显然1只有一个因子，不是素数。

输入描述

第一行一个正整数n，代表kotori拿到正整数的个数。
第二行共有n个数ai，表示每个正整数的值。
保证不存在两个相等的正整数。
1<=n<=10，2<=ai<=1000

输出描述

一个正整数，代表取出的素因子之和的最小值。若不存在合法的取法，则输出-1。

输入

4
12 15 28 22
5
4 5 6 7 8

输出

17
-1

说明

样例1:分别取3，5，7，2，可保证取出的数之和最小

备注

1<=n<=10，2<=ai<=1000

解题思路

题意:每个都贡献一个素因子，保证所有的素因子互不相同，求素因子和的最小值。
思路:线性筛出1~1000之内的所有素数，然后DFS求解最小值。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1005;
const int inf = 0x3f3f3f3f;
bool isprime[MAXM];
int n, cnt = 0, min_ = inf, s[15], pre[MAXM], vis[MAXM];
void prime() {
    isprime[0] = isprime[1] = true;
    for (int i = 2; i < MAXM; i++) {
        if (!isprime[i])
            pre[cnt++] = i;
        for (int j = 0; j < cnt && i * pre[j] < MAXM; j++) {
            isprime[i *pre[j]] = true;
            if (!(i % pre[j]))
                break;
        }
    }
}
void DFS(int x, int ans) {
    if (x >= n) {
        if (min_ > ans)
            min_ = ans;
        return ;    
    }
    for (int i = 0; i < cnt; i++) {
        if (!(s[x] % pre[i]) && !vis[pre[i]]) {
            vis[pre[i]] = true;
            DFS(x + 1, ans + pre[i]);
            vis[pre[i]] = false;
        }
    }
}
int main() {
    prime();
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &s[i]);
    DFS(0, 0);
    if (min_ < inf)
        printf("%d\n", min_);
    else printf("-1\n");
    return 0;
}