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());
        }
    }

}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/387992.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

接口测试方法论

第1章 测试那点事 单元测试》接口测试》界面测试 接口就是包含特定输入和特定输出的一套逻辑处理单元&#xff0c;用户无须知晓接口的内部实现逻辑&#xff0c;这也可以称为接口的黑河处理逻辑。因为服务对象不同&#xff0c;接口又可分为两种&#xff1a;一种是系统或服务的…

LLM Visualization可视化

可视化演示网站&#xff1a;https://bbycroft.net/llm 视频解释&#xff1a;https://www.bilibili.com/video/BV1hZ4y1E7DZ/?spm_id_from333.788&vd_sourcecc2da879c044059d9838f660bcaf4664 欢迎使用Markdown编辑器 你好&#xff01; 这是你第一次使用 Markdown编辑器 …

react【六】 React-Router 路由

文章目录 1、Router1.1 路由1.2 认识React-Router1.3 Link和NavLink1.4 Navigate1.5 Not Found页面配置1.6 路由的嵌套1.7 手动路由的跳转1.7.1 在函数式组件中使用hook1.7.2 在类组件中封装高阶组件 1.8 动态路由传递参数1.9 路由的配置文件以及懒加载 1、Router 1.1 路由 1.…

基于BitVM的乐观 BTC bridge

1. 引言 前序博客&#xff1a; 区块链互操作协议Bitcoin Bridge&#xff1a;治愈还是诅咒&#xff1f;BitVM&#xff1a;Bitcoin的链下合约 基于BitVM的乐观 BTC bridge&#xff1a; Trust-minimized two-way peg 机制 BitVM BTC bridge背后的主要思想是&#xff1a; 为比…

几个经典金融理论

完整EA&#xff1a;Nerve Knife.ex4黄金交易策略_黄金趋势ea-CSDN博客 一、预期效用理论 预期效用理论是描述人们在做出决策时如何考虑风险和不确定性的一种理论。该理论最初由经济学家冯诺伊曼&#xff08;John von Neumann&#xff09;和奥斯卡摩根斯坦恩&#xff08;Oskar…

信号量概念,使用场景,本质,接口函数(pv操作),基于环形队列的生产消费者模型(过程,三个原则,单线程,多线程)

目录 引入​​​​​​​ 介绍 概念 使用场景 引入 介绍 注意 本质 计数器的本质 [判断资源是否就绪] 和互斥锁的关联 接口函数 初始化和销毁信号量 sem_init 函数原型 sem pshared value sem_destroy pv操作 sem_wait ​编辑 sem_post 其他接口 s…

【MySQL进阶之路】MySQL 中的分库分表方案解决方案

欢迎关注公众号&#xff08;通过文章导读关注&#xff1a;【11来了】&#xff09;&#xff0c;及时收到 AI 前沿项目工具及新技术的推送&#xff01; 在我后台回复 「资料」 可领取编程高频电子书&#xff01; 在我后台回复「面试」可领取硬核面试笔记&#xff01; 文章导读地址…

话题——程序员为什么不喜欢关电脑?

程序员为什么不喜欢关电脑&#xff1f; 方向一&#xff1a;工作流程与需求 程序员的工作往往涉及长时间、连续的任务&#xff0c;如代码编写、调试、测试等。这些任务需要高度的集中和专注&#xff0c;而频繁地关机和重启可能会打断他们的工作流&#xff0c;导致他们需要重新…

猫头虎分享已解决Bug || DNS解析问题(DNS Resolution Issue):DNSLookupFailure, DNSResolveError

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

基于决策树的金融市场波动性预测与应用

基于决策树的金融市场波动性预测与应用 项目背景与意义数据概述与分析数据来源数据特征 数据预处理与特征工程模型训练与评估结果与应用总结 LightGBM是一个机器学习算法库&#xff0c;用于梯度提升机&#xff08;Gradient Boosting Machine&#xff09;的实现。梯度提升机是一…

如何书写一个标准JavaBean

前言&#xff1a;在学习Java类的三大特征之一的封装的时候&#xff0c;对封装的数据Java有着自己已经规定好的书写格式&#xff0c;我们需要按照对应的格式进行书写。 我们大致了解一下要学习的内容&#xff1a; 1.封装的概念 如图&#xff08;看不懂没关系&#xff0c;下面会…

iTop-4412 裸机程序(二十二)- RTC时钟

目录 0.源码1. RTC2. iTop4412 中的 RTC使用的相关寄存器3. BCD编码4. 关键源码 0.源码 GitHub&#xff1a;https://github.com/Kilento/4412NoOS 1. RTC RTC是实时时钟&#xff08;Real Time Clock&#xff09;的缩写&#xff0c;是一种用于计算机系统的硬件设备&#xff0…

2024.02.12作业

1. 段错误 2. 段错误 3. hello 4. world 5. int a; int* a; int **a; int a[10]; int* a[10]; int(* a)[10]; int* a(int); int (*a[10])(int); 6. 6&#xff1b; 2&#xff1b; 2 7. 2 8. 2 9. b 10. a 11. a 12. c 13. b 14. c 15. a 16. c 17. b 18. a 19…

【2024年最新指南】掌握国内虚拟卡订阅midjourney的绝佳方法!轻松实现midjourney银行卡支付!(图文详解,简单易懂)

1.Midjourney介绍 Midjourney 是一款备受欢迎的人工智能生成图像工具&#xff0c;它可以通过输入文字描述&#xff0c;自动生成精美的图像。与许多其他图像生成工具不同&#xff0c;Midjourney 不需要安装任何软件&#xff0c;也不受个人电脑性能的限制&#xff0c;因为它运行…

「数据结构」MapSet

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;Java数据结构 &#x1f387;欢迎点赞收藏加关注哦&#xff01; Map&Set &#x1f349;概念&#x1f349;模型&#x1f349;Map&#x1f34c;TreeMap和HashMap的区别&#x1f34c;Map常用方…

第13章 网络 Page727~728 asio定时器例子:后创建的定时器先产生到点事件

代码&#xff1a; 35行&#xff0c;42行&#xff0c;51行&#xff0c;分别构造三个对象&#xff0c; 36行&#xff0c;43行&#xff0c;52行&#xff0c;设置了三个任务peng1、peng2、peng3&#xff0c;并将任务交给io_service对象&#xff08;不需要ios的run()方法启动起来&a…

算法沉淀——队列+宽度优先搜索(BFS)(leetcode真题剖析)

算法沉淀——队列宽度优先搜索&#xff08;BFS&#xff09; 01.N 叉树的层序遍历02.二叉树的锯齿形层序遍历03.二叉树最大宽度04.在每个树行中找最大值 队列 宽度优先搜索算法&#xff08;Queue BFS&#xff09;是一种常用于图的遍历的算法&#xff0c;特别适用于求解最短路径…

文件上传-第三方服务阿里云OSS

JAVA后端实现文件上传,比如图片上床功能,有很多实现方案,可以将图片保存到服务器的硬盘上。也可以建立分布式集群,专门的微服务来存储文件常见的技术比如Minio。对于中小型公司&#xff0c;并且上传文件私密性不高的话可以使用第三方的存储服务&#xff0c;比如阿里云、华为云等…

【51单片机】一个简单的例子TMOD&TCON带你永远理解【(不)可位寻址】

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的《Linux》专栏YY的《数据…

【超级干货】ArcGIS_空间连接_工具详解

帮助里对空间连接的解释&#xff1a; 根据空间关系将一个要素的属性连接到另一个要素。 目标要素和来自连接要素的被连接属性写入到输出要素类。 如上图所示&#xff0c;关键在于空间关系&#xff0c;只有当两个要素存在空间关系的时候&#xff0c;空间连接才有用武之地。 一…