首页分享宠物小精灵之收服（等级考试4级 2021

宠物小精灵之收服（等级考试4级 2021

来源：萌宠菠菠乐园时间：2024-12-28 19:15

题目：

此题目可转化为 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; }