引言
题目链接:https://www.acwing.com/problem/content/1024/
思路
二维费用01背包问题,相比于01背包问题多了一维记录花费。
状态表示:
dp[i][j][k]:表示对于前 i 个精灵,精灵球不超过 j,体力不超过 k 捉到的最大精灵数
状态转移:
对于第 i 个精灵,当前精灵球为 j,体力为 k 时:
-
捉第 i 个精灵:
dp[i][j][k] = dp[j - v1[i]][k - v2[i]] + 1
-
不捉第 i 个精灵:
dp[i][j][k] = dp[i - 1][j][k]
这里要用滚动数组,否则会爆内存。
代码
#include <bits/stdc++.h>
#define N 1010
#define M 510
int n,m,k;
int v1[N],v2[N],dp[N][M]; // dp[i][j]:精灵球不超过i,体力不超过j捉到的最大精灵数
int main() {
std::cin >> n >> m >> k;
for (int i = 1 ; i <= k ; i ++ ) std::cin >> v1[i] >> v2[i];
for (int i = 1 ; i <= k ; i ++ ) {
for (int j = n ; j >= v1[i] ; j -- ) {
for (int k = m - 1 ; k >= v2[i] ; k -- ) {
dp[j][k] = std::max(dp[j][k], dp[j - v1[i]][k - v2[i]] + 1);
}
}
}
int ans1 = dp[n][m - 1],ans2;
for (int i = 0 ; i < m ; i ++ ) {
if(dp[n][i] == ans1) {
ans2 = i;
break;
}
}
std::cout << ans1 << ' ' << m - ans2 << '\n';
return 0;
}
标签:std,int,宠物,精灵,收服,v1,v2,小精灵,dp
From: https://www.cnblogs.com/NachoNeko/p/18004764