asp业务网站/友情链接检测工具

链接：https://ac.nowcoder.com/acm/contest/940/E
来源：牛客网

题目描述

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

她想知道，最终所有取出的数的和的最小值是多少？

注：若a%k==0，则称k是a的因子。若一个数有且仅有两个因子，则称其是素数。显然1只有一个因子，不是素数。

输入描述:

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

输出描述:

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

示例1

输入

4
12 15 28 22

输出

17

说明

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

示例2

输入

5
4 5 6 7 8

输出

-1

备注:

1<=n<=102<=ai<=1000

思路：就是把每个数的素因子都找出来，用vector存起来，然后dfs找最小值

#include <bits/stdc++.h>
using namespace std;
int n;
int vis[1005];
vector<int> v[105];
int ans=999999;
const int MAX = 1000005;
bool prime[MAX];
void init() {memset(prime,true,sizeof prime);for(int i=2; i*i<MAX; i++) {if(prime[i]) {//是素数 for(int j=i*2; j<MAX; j+=i)//从2倍开始，n倍 prime[j]=false;//各个倍数 }}
} 
void dfs(int d,int sum){if(d==n){ans=min(ans,sum);return ;}for(int i=0;i<v[d].size();i++){if(!vis[v[d][i]]){vis[v[d][i]]=1;dfs(d+1,sum+v[d][i]);vis[v[d][i]]=0;}}
}
int main(){init();scanf("%d",&n);for(int i=0;i<n;i++){int temp;scanf("%d",&temp);for(int j=2;j<=temp;j++){if(temp%j==0&&prime[j]){v[i].push_back(j);//cout<<j<<" ";}}//cout<<endl;}dfs(0,0);if(ans==999999)printf("-1\n");elseprintf("%d\n",ans);return 0;
}