每日OJ_牛客_kotori和素因子_DFS_C++_Java

目录

牛客_kotori和素因子_DFS

题目解析

C++代码

Java代码

---

牛客_kotori和素因子_DFS

kotori和素因子

描述：

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

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

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

输入描述：

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

1≤n≤10

2≤ai≤1000

输出描述：

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

---

题目解析

        这道题目要求为数组中的每个数选择一个互不重复的质因数，使得这些质因数的和最小。通过回溯法（DFS）枚举所有可能的质因数组合，并在过程中剪枝和记录最小值，最终可以得到答案。如果没有合法组合，则返回-1。这是一种典型的组合优化问题，适合用深度优先搜索来解决。

C++代码

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
using namespace std;int ret = 0x3f3f3f3f;
bool use[1007]; // 记录路径中⽤了哪些值
int pathSum; // 记录当前路径中所有元素的和
int n = 0;bool is_prime(int n)
{int i = 0;for (i = 2; i <= sqrt(n); i++){if (0 == n % i)return false;}return true;
}void dfs(vector<int>& a, int pos)
{if(pos == n){ret = min(ret, pathSum);return;}for(int i = 2; i <= a[pos]; i++){if(a[pos] % i == 0 && is_prime(i) && !use[i]){pathSum += i;use[i] = true;dfs(a, pos + 1);pathSum -= i;use[i] = false;}}
}int main()
{cin >> n;vector<int> a(n);for(int i = 0; i < n; ++i){cin >> a[i];}dfs(a, 0);if(ret == 0x3f3f3f3f)cout << -1 << endl;elsecout << ret;return 0;
}

Java代码

import java.util.*;
public class Main
{public static int n;public static int[] arr;public static boolean[] use = new boolean[1010]; // 记录路径⾥⾯选了哪些元素public static int path; // 记录路径⾥⾯所有元素的和public static int ret = 0x3f3f3f3f; // 记录最终结果public static boolean isPrim(int x){if(x <= 1)return false;for(int i = 2; i <= Math.sqrt(x); i++){if(x % i == 0) return false;}return true;}public static void dfs(int pos){if(pos == n){ret = Math.min(ret, path);return;}// 枚举 arr[pos] ⾥⾯所有的素因⼦for(int i = 2; i <= arr[pos]; i++){if(arr[pos] % i == 0 && !use[i] && isPrim(i)){path += i;use[i] = true;dfs(pos + 1);// 回溯 - 恢复现场use[i] = false;path -= i;}}}public static void main(String[] args){Scanner in = new Scanner(System.in);n = in.nextInt();arr = new int[n];for(int i = 0; i < n; i++){arr[i] = in.nextInt();}dfs(0);if(ret == 0x3f3f3f3f)System.out.println(-1);elseSystem.out.println(ret);}
}