丰富网站内容,如何做自己的网站,seo推广排名重要吗,电子商务主要干什么1022. 宠物小精灵之收服
题意#xff1a;
现在有n个胶囊#xff0c;m个生命值#xff0c;k个怪物#xff0c;每个怪物需要a[i]个胶囊#xff0c;且会造成b[i]个伤害后才能捕获#xff0c;问在活着的前提下#xff0c;最多捕获多少怪物#xff0c;在怪物最多的情况下剩…1022. 宠物小精灵之收服
题意
现在有n个胶囊m个生命值k个怪物每个怪物需要a[i]个胶囊且会造成b[i]个伤害后才能捕获问在活着的前提下最多捕获多少怪物在怪物最多的情况下剩余生命值最大是多少 数据范围 0N≤1000, 0M≤500, 0K≤100
题解
仔细分析题目就可以得到这个是01背包的延伸01背包中是空间和价钱这个是胶囊和伤害 设f[i][j]表示刚好花费i个胶囊j个生命值所捕获的怪物最大数量 注意f一开始要初始无限大 可以得到转移方程 01背包的延伸
f[0][0] 0;for(int i 1; i K; i) {for(int j n; j w[i]; j--) for(int k m; k v[i]; k--)f[j][k] max(f[j][k], f[j - w[i]][k - v[i]] 1);}然后我们根据最大胶囊的情况选择花费最少的体力值即为剩下最多的体力值 这样复杂度是O(nmk) 详细看代码 但是本题可以优化 我们先想想01背包 体积w与价值v是可以互逆的 什么意思 f[i]表示为体积为i能装的最大价值 我们也可以将f[i]表示为价值为i所需的最小体积 两者等价但是我们只需要选择较小的那个就行 这样可以优化时间复杂度 在本题中k的范围是额外小的所以我们设 dp[i][j]表示正好花费体力i收集j个怪物所用最小的精灵球的数量 这样复杂度是O(K2m) 结合数据范围 O(nmk) 5e7 O(K2m) 5e6 本题是都能过但是这种方法要掌握 图中分别是第二种方法和第一种方法
代码
第一个代码
#include cstdio
#include iostream
#include cstring
using namespace std;
const int N 1005, M 505, S 105;
int n, m, K, w[S], v[S], f[N][M];
int main() {memset(f, 0xcf, sizeof f);scanf(%d%d%d, n, m, K);for(int i 1; i K; i)scanf(%d%d, w i, v i);f[0][0] 0;for(int i 1; i K; i) {for(int j n; j w[i]; j--) for(int k m; k v[i]; k--)f[j][k] max(f[j][k], f[j - w[i]][k - v[i]] 1);}//coutf[0][0]endl;int res 0, t0;for(int j 1; j n; j) {for(int k 1; k m; k) {if(f[j][k] res || (res f[j][k] k t)) {res f[j][k], t k;}}}printf(%d %d\n, res ,m - t);return 0;
}优化后的代码
#include cstdio
#include iostream
#include cstring
using namespace std;
const int N 1005, M 505, S 105;
const int INF 0x3f3f3f3f;
int n, m, K, f[M][S];
/*
f[i][j] 表示体力为 i, 收集了 j 个精灵 用的最小的精灵球数量
*/
int main() {memset(f, 0x3f, sizeof f);scanf(%d%d%d, n, m, K);f[0][0] 0;for (int i 1, c, d; i K; i) {scanf(%d%d, c, d);for (int j m; j d; j--)for (int k K; k 1; k--)if(f[j - d][k - 1] c n)f[j][k] min(f[j][k], f[j - d][k - 1] c);}for (int k K; ~k; k--) {int p INF;for (int j 0; j m; j) {if(f[j][k] ! INF j p) p j;}if(p ! INF) { printf(%d %d\n, k, m - p); return 0; }}return 0;
}
