hdu2639---Bone Collector II(01背包升华)
发布日期:2022-02-02 02:58:10 浏览次数:4 分类:技术文章

本文共 2196 字,大约阅读时间需要 7 分钟。

Problem Description
The title of this problem is familiar,isn't it?yeah,if you had took part in the "Rookie Cup" competition,you must have seem this title.If you haven't seen it before,it doesn't matter,I will give you a link:

Here is the link:

Today we are not desiring the maximum value of bones,but the K-th maximum value of the bones.NOTICE that,we considerate two ways that get the same value of bones are the same.That means,it will be a strictly decreasing sequence from the 1st maximum , 2nd maximum .. to the K-th maximum.

If the total number of different values is less than K,just ouput 0.
 

Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, K(N <= 100 , V <= 1000 , K <= 30)representing the number of bones and the volume of his bag and the K we need. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
 

Output
One integer per line representing the K-th maximum of the total value (this number will be less than 2 31).
 

Sample Input
35 10 21 2 3 4 55 4 3 2 15 10 121 2 3 4 55 4 3 2 15 10 161 2 3 4 55 4 3 2 1
 

Sample Output
1220代码实现:   
   #include 
    
     #include
     
      using namespace std;int num[110];int value[110];int dp[1010][35];int d1[1010];int d2[1010];int main(){
      
int t,n,m,k,x,y,z,p;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>value[i];
for(int i=1;i<=n;i++)
cin>>num[i];
for(int i=1;i<=n;i++)
{
for(int j=m;j>=num[i];j--)
{
for(p=1;p<=k;p++)
{
d1[p]=dp[j][p];
d2[p]=dp[j-num[i]][p]+value[i];
}
d1[p]=d2[p]=-1;
x=y=z=1;
while((d1[x]!=-1||d2[y]!=-1)&&z<=k)
{
if(d1[x]>d2[y])
{
dp[j][z]=d1[x];
x++;
}
else
{
dp[j][z]=d2[y];
y++;
}
if(dp[j][z-1]!=dp[j][z])
z++;
}
}
}
   cout< <
   }
return 0;}


转载地址:https://blog.csdn.net/u010368749/article/details/20045987 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu1171---Big Event in HDU(多重背包)
下一篇:hdu2955---Robberies(01背包)

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.249.68.14]2022年05月23日 01时25分01秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 2019-08-03 02:38:22
synchronized 不是万能,错误加锁 2019-08-03 02:38:22
给定一个二叉树,判断它是否是高度平衡的二叉树。 2019-08-03 02:38:21
老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 2019-08-03 02:38:21
Thread 和 Runnable 区别? 2019-08-03 02:38:20
Mybatis 2019-08-03 02:38:20
在二维平面上,有一个机器人从原点 (0, 0) 开始。给出它的移动顺序,判断这个机器人在完成移动后是否在 (0, 0) 处结束。 2019-08-03 02:38:19
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 2019-08-03 02:38:19
给出 N 名运动员的成绩,找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”,“银牌” 和“ 铜牌” 2019-08-03 02:38:19
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 2019-08-03 02:38:18
验证回文串 2019-08-03 02:38:18
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 2019-08-03 02:38:18
设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。 2019-08-03 02:38:17
数据库为什么用事务、事务的特性、事务的并发问题以及事务的隔离级别 2019-08-03 02:38:17
数据库优化 2019-08-03 02:38:16
Unix和Linux有什么区别? 2019-08-03 02:38:16
【Python】之海龟图形化程序 2019-08-03 02:38:15
什么是Python? 2019-08-03 02:38:15
Redis持久化 2019-08-03 02:38:15
给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 2019-08-03 02:38:14