1022. 寵物小精靈之收服

題意：

現在有n個膠囊，m個生命值，k個怪物，每個怪物需要a[i]個膠囊，且會造成b[i]個傷害后才能捕獲，問在活著的前提下，最多捕獲多少怪物，在怪物最多的情況下剩余生命值最大是多少
數據范圍：
0<N≤1000,
0<M≤500,
0<K≤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(K²m)
結合數據范圍：
O(nmk) = 5e7
O(K²m) = 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);}//cout<<f[0][0]<<endl;int res = 0, t=0;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; }

總結

以上是生活随笔為你收集整理的1022. 宠物小精灵之收服的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。