本文主要是介绍AtCoder Beginner Contest 332 --- E - Lucky bag --- 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
E - Lucky bag
题目大意：
思路解析：
代码实现：
E - Lucky bag
题目大意：
思路解析：
在方差中平均值只与输入有关为定值。看到数据范围为 2 <= D <= N <= 15，想到是否能使用状压dp来进行解答。
dp[i][j] （i为二进制）表示 i二进制状态下选择了这么多个物品，使用j个背包能够达到最小的方差。
代码实现：
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int mod1 = (int) 1e9 + 7;static int mod2 = 998244353;static int BD = 500;public static void main(String[] args) throws IOException {int n = input.nextInt();int d = input.nextInt();int[] arr = new int[n];double sum = 0;for (int i = 0; i < n; i++) {arr[i] = input.nextInt();sum += arr[i];}sum /= d;double[][] dp = new double[(1 << n)][d + 1];for (int i = 0; i < (1 << n); i++) {double y = 0;for (int j = 0; j < n; j++) {if ((i & (1 <<j)) != 0)y+=arr[j];}dp[i][1] = Math.pow(y-sum, 2);for (int j = 2; j <= d; j++) {dp[i][j] = dp[i][j-1] + dp[0][1];int x = i;while (x > 0){dp[i][j] = Math.min(dp[i][j], dp[i-x][j-1] + dp[x][1]);x = (x - 1) & i;}}}out.printf("%.15f",dp[(1 << n) - 1][d] / d);out.flush();out.close();br.close();}// -------------------------------- 模板 ---------------------------static boolean nextPermutation(int[] arr) { // 排列数循环模板 记得使用 do while 循环int len = arr.length;int left = len - 2;while (left >= 0 && arr[left] >= arr[left + 1]) left--; // 从升序 一直往降序排列。if (left < 0) return false;int right = len - 1;// 找到第一个升序的位置，将其改为降序。while (arr[left] >= arr[right]) right--;{int t = arr[left];arr[left] = arr[right];arr[right] = t;}// 修改后它的前面仍然为降序，将前面全部修改为升序，这样能保证不会漏算，也不会算重left++;right = len - 1;while (left < right) {{int t = arr[left];arr[left] = arr[right];arr[right] = t;}left++;right--;}
// System.out.println(Arrays.toString(arr));return true;}public static long qkm(long a, long b, long mod) { // 快速幂模板long res = 1;while (b > 0) {if ((b & 1) == 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;}// // 线段树模板
// public static int lowbit(int x){
// return x & (-x);
// }
//
// public static void bulid(int n){
// for (int i = 1; i <= n; i++) {
// t[i] = a[i];
// int j = i + lowbit(i);
// if (j<=n) t[j] += t[i];
// }
// }
//
// public static void updata(int x, int val){
// while (x <= n){
// t[x] += val;
// x += lowbit(x);
// }
// }
//
// public static int query(int l, int r){
// int res = 0;
// while (l <= r){
// res += a[r];
// r--;
// while (r - lowbit(r) >= l){
// res += t[r];
// r -= lowbit(r);
// }
// }
// return res;
// }static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static Input input = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}}
这篇关于AtCoder Beginner Contest 332 --- E - Lucky bag --- 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
