当前位置: 首页 > news >正文

[补题记录] Atcoder Beginner Contest 322(E)

URL:https://atcoder.jp/contests/abc322

目录

E

Probelm/题意

Thought/思路

Code/代码


E

Probelm/题意

有 N 个改进计划,每个计划可以执行一次;有 K 个参数,每个计划可以将所有参数提升固定值,即计划 i 可以为第 j 个参数提升 Aij 的数值。每个计划有花费 Ci,问最少多少花费,能让所有参数都 >= P。

其中 1 <= K, P <= 5;1 <= N <= 100。

Thought/思路

假如只有一个参数,我们很容易想到这是一个 dp。比如:

dp[i][A1] = min(dp[i][A1], dp[i - 1][0 + A1])

dp[i][x] = min(dp[i][x], dp[i - 1][x - A1])


但是现在有 K 个参数,也就是说,我们无法确定 dp 数组的维度。

考虑 K = 5 的情况,就会有 dp[i][A1][A2][A3][A4][A5];再考虑一个参数时,我们是如何得到答案的,显然是通过维护 dp[i][0] ~ dp[i][P] 的最小值来的得到答案 dp[n][P]。

那么我们就可以这样做,将参数 [A1][A2][A3] 视作一系列 P + 1 进制的数(因为需要到达 P),如:[0][0][0] ~ [5][5][5] 就是一系列 3 位的 6 进制数。


这样,就可以将不确定的维度,转换为一维的:dp[i][0 ~ pow(P + 1, K) - 1]。

当我们在状态转移的时候,就可以将十进制的整数,转换为 K 进制数组,对应每个计划的 Aij,算出需要维护的 dp 下一个状态。

Code/代码

#include "bits/stdc++.h"#define int long longconst int inf = 1e15;int n, k, p, dp[107][8003];std::vector <int> tenToK(int x, int k, int bit) { // k 进制std::vector <int> res(bit);for (int i = 0; i < bit; ++ i) {res[i] = x % k;x /= k;}std::reverse(res.begin(), res.end());return res;
}int kToTen(std::vector <int> x, int k, int bit) {int res = 0;for (int i = 0; i < bit; ++ i) {res = res * k + x[i];}return res;
}signed main() {std::cin >> n >> k >> p;int size = (int)std::pow(p + 1, k);for (int i = 0; i <= n; ++ i) {for (int j = 0; j < size; ++ j) {dp[i][j] = inf;}}dp[0][0] = 0;for (int i = 1; i <= n; ++ i) {int c; std::cin >> c;std::vector <int> a(k);for (int j = 0; j < k; ++ j) {std::cin >> a[j];}for (int j = 0; j < size; ++ j) dp[i][j] = dp[i - 1][j]; // 不选 i 的情况for (int j = 0; j < size; ++ j) {std::vector <int> now = tenToK(j, p + 1, k);for (int l = 0; l < k; ++ l) now[l] = std::min(p, now[l] + a[l]);int next = kToTen(now, p + 1, k);dp[i][next] = std::min(dp[i][next], dp[i - 1][j] + c);}}std::cout << (dp[n][size - 1] == inf ? -1 : dp[n][size - 1]);
}

相关文章:

[补题记录] Atcoder Beginner Contest 322(E)

URL&#xff1a;https://atcoder.jp/contests/abc322 目录 E Probelm/题意 Thought/思路 Code/代码 E Probelm/题意 有 N 个改进计划&#xff0c;每个计划可以执行一次&#xff1b;有 K 个参数&#xff0c;每个计划可以将所有参数提升固定值&#xff0c;即计划 i 可以为第…...

目标检测算法改进系列之Backbone替换为FocalNet

FocalNet 近些年&#xff0c;Transformers在自然语言处理、图像分类、目标检测和图像分割上均取得了较大的成功&#xff0c;归根结底是自注意力&#xff08;SA &#xff1a;self-attention&#xff09;起到了关键性的作用&#xff0c;因此能够支持输入信息的全局交互。但是由于…...

buuctf-[BSidesCF 2020]Had a bad day 文件包含

打开环境 就两个按钮&#xff0c;随便按按 url变了 还有 像文件包含&#xff0c;使用php伪协议读取一下&#xff0c;但是发现报错&#xff0c;而且有两个.php,可能是自己会加上php后缀 所以把后缀去掉 /index.php?categoryphp://filter/convert.base64-encode/resourcei…...

Elasticsearch:什么时候应该考虑在 Elasticsearch 中添加协调节点?

仅协调节点&#xff08;coordinating only nodes&#xff09;充当智能负载均衡器。 仅协调节点的这种特殊角色通过减轻数据和主节点的协调责任&#xff0c;为广泛的集群提供了优势。 加入集群后&#xff0c;这些节点与任何其他节点类似&#xff0c;都会获取完整的集群状态&…...

Dubbo3应用开发—Dubbo注册中心引言

Dubbo注册中心引言 什么是Dubbo注册中心 Dubbo的注册中心&#xff0c;是Dubbo服务治理的⼀个重要的概念&#xff0c;他主要用于 RPC服务集群实例的管理。 注册中心的运行流程 使用注册中心的好处 可以有效的管理RPC集群的健康情况&#xff0c;动态的上线或者下线服务。让我…...

AS环境,版本问题,android开发布局知识

项目模式下有一个build.gradle,每个模块也有自己的build.gradle Android模式下有多个build.gradle&#xff0c;汇总在一起。&#xff08;都会有标注是哪个模块下的&#xff09; C:\Users\Administrator\AndroidStudioProjects 项目默认位置 Java web项目与android项目的区别…...

OpenCV查找和绘制轮廓:findContours和drawContours

1 任务描述&#xff1a; 绘制图中粗线矩形的2个边界&#xff0c;并找到其边界的中心线 图1 原始图像 2.函数原型 findContours( InputOutputArray image, OutputArrayOfArrays contours, OutputArray hierarchy, int mode, …...

毕设-原创医疗预约挂号平台分享

医疗预约挂号平台 不是尚医通项目&#xff0c;先看项目质量&#xff08;有源码论文&#xff09; 项目链接&#xff1a;医疗预约挂号平台git地址 演示视频&#xff1a;医疗预约挂号平台 功能结构图 登录注册模块&#xff1a;该模块具体分为登录和注册两个功能&#xff0c;这些…...

PLL锁相环倍频原理

晶振8MHz&#xff0c;但是处理器输入可以达到72MHz&#xff0c;是因为PLL锁相环提供了72MHz。 锁相环由PD&#xff08;鉴相器&#xff09;、LP&#xff08;滤波器&#xff09;、VCO&#xff08;压控振荡器&#xff09;组成。 处理器获得的72MHz并非晶振提供&#xff0c;而是锁…...

POJ 2886 Who Gets the Most Candies? 树状数组+二分

一、题目大意 我们有N个孩子&#xff0c;每个人带着一张卡片&#xff0c;一起顺时针围成一个圈来玩游戏&#xff0c;第一回合时&#xff0c;第k个孩子被淘汰&#xff0c;然后他说出他卡片上的数字A&#xff0c;如果A是一个正数&#xff0c;那么下一个回合他左边的第A个孩子被淘…...

阿里云服务器镜像系统Anolis OS龙蜥详细介绍

阿里云服务器Anolis OS镜像系统由龙蜥OpenAnolis社区推出&#xff0c;Anolis OS是CentOS 8 100%兼容替代版本&#xff0c;Anolis OS是完全开源、中立、开放的Linux发行版&#xff0c;具备企业级的稳定性、高性能、安全性和可靠性。目前阿里云服务器ECS可选的Anolis OS镜像系统版…...

数学建模Matlab之基础操作

作者由于后续课程也要学习Matlab&#xff0c;并且之前也进行了一些数学建模的练习&#xff08;虽然是论文手&#xff09;&#xff0c;所以花了几天零碎时间学习Matlab的基础操作&#xff0c;特此整理。 基本运算 a55 %加法&#xff0c;同理减法 b2^3 %立方 c5*2 %乘法 x 1; …...

[计算机入门] Windows附件程序介绍(工具类)

3.14 Windows附件程序介绍(工具类) 3.14.1 计算器 Windows系统中的计算器是一个内置的应用程序&#xff0c;提供了基本的数学计算功能。它被设计为一个方便、易于使用的工具&#xff0c;可以满足用户日常生活和工作中的基本计算需求。 以下是计算器程序的主要功能&#xff1a…...

队列(循环数组队列,用队列实现栈,用栈实现队列)

基础知识 队列(Queue):先进先出的数据结果,底层由双向链表实现 入队列:进行插入操作的一端称为队尾出队列:进行删除操作的一端称为对头 常用方法 boolean offer(E e) 入队 E(弹出元素的类型) poll() 出队 peek() 获取队头 int size 获取队列元素个数 boolean isEmpty(…...

卷积神经网络-池化层和激活层

2.池化层 根据特征图上的局部统计信息进行下采样&#xff0c;在保留有用信息的同时减少特征图的大小。和卷积层不同的是&#xff0c;池化层不包含需要学习的参数。最大池化(max-pooling)在一个局部区域选最大值作为输出&#xff0c;而平均池化(average pooling)计算一个局部区…...

API基础————包

什么是包&#xff0c;package实际上就是一个文件夹&#xff0c;便于程序员更好的管理维护自己的代码。它可以使得一个项目结构更加清晰明了。 Java也有20年历史了&#xff0c;这么多年有这么多程序员写了无数行代码&#xff0c;其中有大量重复的&#xff0c;为了更加便捷省时地…...

【C++】一文带你走入vector

文章目录 一、vector的介绍二、vector的常用接口说明2.1 vector的使用2.2 vector iterator的使用2.3 vector空间增长问题2.4 vector 增删查改 三、总结 ヾ(๑╹◡╹)&#xff89;" 人总要为过去的懒惰而付出代价ヾ(๑╹◡╹)&#xff89;" 一、vector的介绍 vector…...

《Secure Analytics-Federated Learning and Secure Aggregation》论文阅读

背景 机器学习模型对数据的分析具有很大的优势&#xff0c;很多敏感数据分布在用户各自的终端。若大规模收集用户的敏感数据具有泄露的风险。 对于安全分析的一般背景就是认为有n方有敏感数据&#xff0c;并且不愿意分享他们的数据&#xff0c;但可以分享聚合计算后的结果。 联…...

十三、Django之添加用户(原始方法实现)

修改urls.py path("user/add/", views.user_add),添加user_add.html {% extends layout.html %} {% block content %}<div class"container"><div class"panel panel-default"><div class"panel-heading"><h3 c…...

Elasticsearch数据操作原理

Elasticsearch 是一个开源的、基于 Lucene 的分布式搜索和分析引擎&#xff0c;设计用于云计算环境中&#xff0c;能够实现实时的、可扩展的搜索、分析和探索全文和结构化数据。它具有高度的可扩展性&#xff0c;可以在短时间内搜索和分析大量数据。 Elasticsearch 不仅仅是一个…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...