这一题是二维费用的背包问题。
状态表示:f[i][j][k]
表示收服前i
个小精灵的消耗j
个精灵球的损失k
个体力值的选法的集合,属性为max
.
状态计算:分为收服与不收服两种状态。
由题意可得,本题有两种费用,一是消耗的精灵球的数量,二是皮卡丘消耗的体力值。于是要写两重循环来解决问题。于是,我们直接来看一下二维的01
背包到底怎么写。
#include<bits/stdc++.h>
using namespace std;
const int A = 1010,B = 510;
int N,M,n;
int f[A][B];
int main()
{
cin>>N>>M>>n;
for(int i=1;i<=n;i++)
{
int v1,v2;//收服第i个精灵所需要的精灵球的数量和体力值
cin>>v1>>v2;
for(int j=N;j>=v1;j--)//枚举精灵球数量的状态
for(int k=M-1;k>=v2;k--)//枚举体力值状态,因为收服精灵所受到的伤害大于等于当前体力值就无法被收服,所以k从(M-1)开始取
f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);
}
cout<<f[N][M-1]<<' ';
int min_use=M-1;//与上面同理,消耗的最大体力值是(M-1)
while(min_use>0&&f[N][min_use-1]==f[N][min_use])min_use--;//这里min_use>0是因为(min_use-1)>=0
cout<<M-min_use;//输出最大剩余体力
}