uva 12563 01背包 两个最优条件 lrj-P274

本文主要是介绍uva 12563 01背包 两个最优条件 lrj-P274，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给你 t 秒时间，有n首歌，每一首歌的时间不超过三分钟，在结束之前唱一首678秒的劲歌金曲

选了一首歌就一定要唱完

并且在保持唱的歌曲数量最多的情况下，时间最长

题解：

虽然 t 的范围很大，有十的九次方，但是n最多只有50 ，所以不会总时间超过 180*50+678 秒

此时就可以用01背包了，但是有两个最优条件

用结构体存，并且重载小于符合，设置优先级，见代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int a[100];
struct node
{int s;int time;bool operator<(const node &rhs)const//判断是否更优{return s<rhs.s || (s==rhs.s && time<rhs.time);}
}dp[11000],p;int main()
{int cases=1,n,t,T;//freopen("in.txt","r",stdin);scanf("%d",&T);while(T--){int sum=0,temp,ans=0;scanf("%d%d",&n,&t);for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}memset(dp,0,sizeof(dp));temp=min(sum,t-1);for(int i=1;i<=n;i++){for(int j=temp;j>=a[i];j--){p.s=dp[j-a[i]].s+1;p.time=dp[j-a[i]].time+a[i];if(dp[j]<p) dp[j]=p;}}printf("Case %d: %d %d\n",cases++,dp[temp].s+1,dp[temp].time+678);}return 0;
}

这篇关于uva 12563 01背包 两个最优条件 lrj-P274的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---