北京信息科技大学第十一届程序设计竞赛（重现赛）E kotori和素因子

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

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

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

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

打表筛出每个数的质因子，然后深搜求解最小值

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<LL,LL>
#define PCC pair<char,char>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1

const int N=1e3+7;
const int INF=1e8,mod=1e8;

vector<int>v[N];
int f[N];
int n,a[N];
int ans;
int b[N];

void dfs(int x,int y){
    if(x>n){
        ans=min(ans,y);
        return;
    }
    for(int i=0;i<v[a[x]].size();i++){
        if(!f[v[a[x]][i]]){
            f[v[a[x]][i]]=1;
            b[x]=v[a[x]][i];
            dfs(x+1,y+v[a[x]][i]);
            f[v[a[x]][i]]=0;
        }
    }
}

int main()
{
    ans=INF;
    for(int i=2;i<=1000;i++){
        if(!f[i]){
            v[i].PB(i);
            for(int j=i+i;j<=1000;j+=i){
                v[j].PB(i);
                f[j]=1;
            }
        }
    }
    memset(f,0,sizeof(f));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1,0);
    if(ans==INF)cout<<-1;
    else cout<<ans;
    return 0;
}