青海省住房建设厅网站首页,网站建设与设计教程视频,flash 制作网站,介绍什么是网页设计目录
E - Lucky bag
题目大意#xff1a;
思路解析#xff1a;
代码实现#xff1a; E - Lucky bag
题目大意#xff1a; 思路解析#xff1a; 在方差中平均值只与输入有关为定值。看到数据范围为 2 D N 15#xff0c;想到是否能使用状压dp来进行解答…目录
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)yarr[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 (jn) 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());}}}
