洛谷 U266184 宠物小精灵之收服

题目链接：宠物小精灵之收服 - 洛谷

标签：dp、背包问题

思路：

精灵球个数 与 对皮卡丘的伤害 都可以看成背包问题中的体积，所以将dp数组升级为二维

dp[i][j]表示 i个精灵球 j滴血皮卡丘 最多可以收服多少小精灵。

得到转移方程 dp[i][j] = max(dp[i-v1][j-v2]+1,dp[i][j])

注意点：洛谷测评所用数据与题目描述不一致，将dp数组开成1005×5005才通过

AC代码：

#include<iostream>

using namespace std;

int dp[1005][5005];

int main()

{

int n,m,num;

cin>>n>>m>>num;

int v1,v2;

for(int i=1;i<=num;++i)

{

cin>>v1>>v2;

for(int j=n;j>=v1;j--)

{

for(int k=m;k>v2;k--)

{

dp[j][k]=max(dp[j][k],dp[j-v1][k-v2]+1);

}

}

}

if(dp[n][m]==0) cout<<"0 "<<m<<endl;

else for(int i=m;i>0;i--)

{

if(dp[n][i]<dp[n][m])

{

cout<<dp[n][m]<<" "<<m-i;

break;

}

}

return 0;

}