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

el/2024/2/25 22:21:27

题意:

给你 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;
}



http://www.ngui.cc/el/4895176.html

相关文章

uva 11400 lrj-P275 动态规划

题意&#xff1a; 见刘汝佳入门书籍 P275 dp[i]min(dp[i],dp[j-1](sum[i]-sum[j-1])*a[i].ca[i].k);题解&#xff1a; 见刘汝佳入门书籍 P275 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std;int dp[1010],sum[1010]; s…

密码生成器+随机数生成器

随机数生成器 0~RAND_MAX之间的随机数程序 #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int main() {srand((unsigned)time(NULL));for(int i = 0; i < 10; i++ )cout << rand() << \t;cout << …

uva 10003 lrj-P278 区间dp入门

题意&#xff1a; 给出一根棍子的长度&#xff0c;以及n个需要切割的点&#xff0c;每一次切割的代价是这一段需要被切割的长度 问代价最小时的代价值 题解&#xff1a; 区间dp dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]a[j]-a[i]); i 为区间左端点&#xff0c;j 为右端点…

Uva-1626 lrj-P278 区间dp

题意&#xff1a; 给定一个由[,],(,)&#xff0c;构成的字符串&#xff0c;给其添加这些括号使得其成为一个正规括号序列 1 空序列是正规括号序列 2 如果S是正规括号序列&#xff0c;那么[S]和(S)也是正规括号序列 3 如果A和B都是正规括号序列&#xff0c;则AB也是正规…

uva 1331 lrj-P279 三角剖分+区间dp

题意&#xff1a; 给出多边形&#xff0c;找出最大三角形面积最小的三角剖分 输出最大的三角形面积 题解&#xff1a; 仔细研究可以知道&#xff0c;第一个点和最后一个点组成的边&#xff0c;一定是在某一个三角形中 那么我们就通过这个边作为基准&#xff0c;任选一个…

uva 12186 lrj-P282 简单树形dp

题意&#xff1a; 某个人签字的话,他的直属下属里必须有至少T%的人签字,问让老板签字最少需要多少工人签字 题解&#xff1a; 树形dp 以老板为根节点&#xff0c;从小往上&#xff0c;递归计算答案即可 #include<vector> #include<stdio.h> #include<st…

uva 1220 lrj-P282 最大独立集(树形dp)

题意&#xff1a; 给出一个树形结构&#xff0c;除了老板外&#xff0c;每一个员工都有直属上司&#xff0c;在其中挑选了员工&#xff0c;就不能挑选他的上司 问这样的挑选方法最多可以挑选多少人&#xff0c;方案是否唯一 题解&#xff1a; 仔细划分即可 当前节点若选…

uva 10285 lrj-P304 从简单DAG动态规划得到的感悟

题意&#xff1a; 给出一个整数矩阵&#xff0c;请找出一条严格递减的最长路的长度 题解&#xff1a; 分析&#xff1a; 1没有固定起点和终点 2是二元关系&#xff0c;也就是DAG&#xff08;有向无环图&#xff09; 3lrj书上此类一律都是用记忆化搜索 假设&#xff…

uva 1630 lrj-P305 字符串dp(记忆化)

题意&#xff1a; 给出一个字符串&#xff0c;然后要你把他折叠成一个最短的字符串 例如 AAAAAAAAAABABABCCD NEERCYESYESYESNEERCYESYESYES 变成&#xff1a; 9(A)3(AB)CCD 2(NEERC3(YES) 题解&#xff1a; 很容易看出来用分治的办法&#xff0c;但是不会把折叠起来&a…

hdu 6206 模板题 2017 ACM/ICPC Asia Regional Qingdao Online

下面的模板来自于 http://blog.csdn.net/liyuanbhu/article/details/52891868 三点确定一个圆的计算方法 最近在写的一个软件需要根据三个坐标点来计算一个圆。因此花了点时间推导了相关的公式。这个推导不算太难&#xff0c;放在这里主要是做个备忘。 我们设一个圆的圆…