当前位置: 首页 > 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]);
}
http://www.lryc.cn/news/183291.html

相关文章:

  • 目标检测算法改进系列之Backbone替换为FocalNet
  • buuctf-[BSidesCF 2020]Had a bad day 文件包含
  • Elasticsearch:什么时候应该考虑在 Elasticsearch 中添加协调节点?
  • Dubbo3应用开发—Dubbo注册中心引言
  • AS环境,版本问题,android开发布局知识
  • OpenCV查找和绘制轮廓:findContours和drawContours
  • 毕设-原创医疗预约挂号平台分享
  • PLL锁相环倍频原理
  • POJ 2886 Who Gets the Most Candies? 树状数组+二分
  • 阿里云服务器镜像系统Anolis OS龙蜥详细介绍
  • 数学建模Matlab之基础操作
  • [计算机入门] Windows附件程序介绍(工具类)
  • 队列(循环数组队列,用队列实现栈,用栈实现队列)
  • 卷积神经网络-池化层和激活层
  • API基础————包
  • 【C++】一文带你走入vector
  • 《Secure Analytics-Federated Learning and Secure Aggregation》论文阅读
  • 十三、Django之添加用户(原始方法实现)
  • Elasticsearch数据操作原理
  • gitgitHub
  • 十天学完基础数据结构-第九天(堆(Heap))
  • vertx的学习总结7之用kotlin 与vertx搞一个简单的http
  • golang学习笔记(二):链路追踪
  • git提交代码实际操作
  • TF坐标变换
  • 如何进行网络编程和套接字操作?
  • 在Spark中集成和使用Hudi
  • 力扣第226翻转二叉数 c++三种方法 +注释
  • React项目部署 - Nginx配置
  • 【Vue3】定义全局变量和全局函数