宠物小精灵之收服（等级考试4级 2021
题目：
此题目可转化为 01背包问题
dp[ i ] [ j ] [ l ] 表示i个精灵球、j点体力、l 个精灵时最多收复精灵的个数。
注意事项：开三维数组一定要贴着给的数据开，本题中开dp[1001][501][101],否则容易爆。
遍历范围：
i:1~n
j：1~m
l：1~k
w[l]: 需要消耗的精灵球数量
v[l]：需要消耗的体力值
状态转移方程：
if(i>=w[l]&&j>v[l]) //余下的精灵球数量足够、体力也足够。
{
dp[i][j][l]=max(dp[i-w[l]][j-v[l]][l-1]+1,dp[i][j][l-1]);// 前者为取第l 个精灵 后者为不取。
}
else
{
dp[i][j][l]=dp[i][j][l-1];
}
最后输出捕捉最多精灵后剩余的最大体力。
k1指用掉多少点能量。
k1从m开始向下减，直到dp[n][k1][l]与dp[n][m][k]不相同时输出m-k1即余下的体力。
程序：
#include<bits/stdc++.h> using namespace std; int dp[1001][501][101]; int main() { int n,m,k,w[1010],v[1010]; cin>>n>>m>>k; for(int i=1;i<=k;i++) { scanf("%d%d",&w[i],&v[i]); } int m2=m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int l=1;l<=k;l++) { if(i>=w[l]&&j>v[l]) { if(dp[i-w[l]][j-v[l]][l-1]+1>dp[i][j][l-1]) { m2-=v[l]; dp[i][j][l]=dp[i-w[l]][j-v[l]][l-1]+1; } else { dp[i][j][l]=dp[i][j][l-1]; } } else { dp[i][j][l]=dp[i][j][l-1]; } } } } cout<<dp[n][m][k]<<" "; int k1=m; while(k1>0&&dp[n][k1][k]==dp[n][m][k]) k1--; cout<<m-k1; return 0; }
相关知识
宠物小精灵之收服
4978:宠物小精灵之收服
Bailian4102 宠物小精灵之收服【模拟】
T1292：宠物小精灵之收服
[Acwing1022]宠物小精灵之收服
4102:宠物小精灵之收服
宠物小精灵之收服（二维背包）
AcWing 1022. 宠物小精灵之收服
1292：宠物小精灵之收服
【openjudge】宠物小精灵之收服
网址: 宠物小精灵之收服（等级考试4级 2021 https://m.mcbbbk.com/newsview906004.html
| 上一篇: 【宠物小精灵4】宠物小精灵4游戏 |
下一篇: 宠物触痕UI图标 |
