wordpress做一个视频网站吗,装修加盟,搞笑视频网站建设策划书,家乡网站设计模板URL#xff1a;https://atcoder.jp/contests/abc322 目录
E
Probelm/题意
Thought/思路
Code/代码 E
Probelm/题意
有 N 个改进计划#xff0c;每个计划可以执行一次#xff1b;有 K 个参数#xff0c;每个计划可以将所有参数提升固定值#xff0c;即计划 i 可以为第…URLhttps://atcoder.jp/contests/abc322 目录
E
Probelm/题意
Thought/思路
Code/代码 E
Probelm/题意
有 N 个改进计划每个计划可以执行一次有 K 个参数每个计划可以将所有参数提升固定值即计划 i 可以为第 j 个参数提升 Aij 的数值。每个计划有花费 Ci问最少多少花费能让所有参数都 P。
其中 1 K, P 51 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]);
}
