首页 > 代码库 > 【noi 2.6_4978】宠物小精灵之收服(DP)
【noi 2.6_4978】宠物小精灵之收服(DP)
题意:小智有N个精灵球,皮卡丘有M的初始体力,有K个野生小精灵。要收服尽可能多的野生小精灵,并使皮卡丘的剩余体力最大。
解法:01背包问题,增多一维来存第二个条件。f[i][j][k]表示抓前i个野生小精灵,用了j个精灵球,耗费了k的体力时能抓的最多的小精灵数。(我把[i]的那维简化掉了,PG里的m代替N,v代替M,n代替K。)
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define INF 1e6 7 8 int a[110],b[110]; 9 int f[1010][510];10 11 int main()12 {13 int m,v,n;14 scanf("%d%d%d",&m,&v,&n);15 for (int i=1;i<=n;i++)16 scanf("%d%d",&a[i],&b[i]);17 int mx=0,ans=0;18 memset(f,0,sizeof(f));19 for (int i=1;i<=n;i++)20 for (int j=m;j>=a[i];j--)21 for (int k=v;k>=b[i];k--)22 {23 f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+1);24 if (f[j][k]>mx||(f[j][k]==mx && v-k>ans)) mx=f[j][k],ans=v-k;25 }26 if (!mx) ans=v;27 printf("%d %d\n",mx,ans);28 return 0;29 }
【noi 2.6_4978】宠物小精灵之收服(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。