本文共 1521 字，大约阅读时间需要 5 分钟。

题目链接：

题目描述

kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。

输入描述

第一行一个正整数n，代表kotori拿到正整数的个数。

输出描述

一个正整数，代表取出的素因子之和的最小值。若不存在合法的取法，则输出-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

解题思路

题意:每个都贡献一个素因子，保证所有的素因子互不相同，求素因子和的最小值。

Accepted Code:

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

转载地址：https://lzyws739307453.blog.csdn.net/article/details/94550443 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！