HDU 2639

Bone Collector II

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 883 Accepted Submission(s): 411

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:http://acm.hdu.edu.cn/showproblem.php?pid=2602

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 231).

Sample Input
3
5 10 2
1 2 3 4 5
5 4 3 2 1
5 10 12
1 2 3 4 5
5 4 3 2 1
5 10 16
1 2 3 4 5
5 4 3 2 1

Sample Output
12
2

0

先全部存起来,再排序,再开一个数组遇到不同的就存起来。

#include <string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int f[1005][35],temp[65];
int w[105],c[105];
int main()
{
    int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,vol,kth;
	   	scanf("%d%d%d",&n,&vol,&kth);
		int i,j,k,cns;
		for(i=0;i<n;i++)
		scanf("%d",&w[i]);
		for(i=0;i<n;i++)
		scanf("%d",&c[i]);
		memset(f,0,sizeof(f));
		for(i=0;i<n;i++)
		{
			for(j=vol;j>=c[i];j--)
			{
				 cns=0;
				for(k=0;k<kth;k++)
				{
					temp[cns++]=f[j][k];
					temp[cns++]=f[j-c[i]][k]+w[i];
				}
				sort(temp,temp+cns);
				     int p=0;
				for(k=cns-1;k>=0;k--)
				{
					if(p>=kth)
						break;
					if(k==cns-1 || temp[k]!=temp[k+1])
						f[j][p++]=temp[k];
				}
			}
		}
	      printf("%d\n",f[vol][kth-1]);
	}
	return 0;
}
时间: 2024-10-22 20:43:04

HDU 2639的相关文章

hdu 2639 Bone Collector II (0/1背包)

点击打开链接hdu 2639 思路: 0/1背包求第k优解 分析: 1 其基本思想是,将每个状态都表示成有序队列,将状态转移方程中的 max/min 转 化成有序队列的合并. 2 这里仍然以 01 背包为例讲解一下.    首先看 01 背包求最优解的状态转移方程: F [i, v] = max{F [i − 1, v], F [i − 1, v −Ci ] + Wi }.如果要求第 K 优解,那么状态 F [i, v] 就应该是一个大小为 K 的队列F [i, v, 1 . . . K].其中

算法:hdu 2639 Bone Collector II (dp 01背包求第k优解)

题目大意: 有n件物品,每件物品有体积和价值两个属性, 一个小偷带着一个大小为v的背包,要 偷这些东西,问小偷能偷的第k大的价值是多少? 思路: 这题和典型的01背包求最优解不同, 是要求第k大的解,所以,最直观的想法就是在01背包的基础上再增加一维,用来保存前k大小的数,然后在 递推时,根据前一个状态的前k 大小的数推出下一个阶段的前k个数保存下来. d[i][j][k], 表示取前i个物品,用j的费用,第k大价值是多少 在递推d[i][j][1...k]时,先获取上一个状态d[i- 1][j

HDU 2639(第K大背包)

Bone Collector II Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 917 Accepted Submission(s): 437 Problem Description The title of this problem is familiar,isn't it?yeah,if you had took part in the

hdu 1527

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1527 hint:威佐夫博弈 基本类似于模板 #include <iostream> #include <cmath> #include <cstdio> using namespace std; const double q = (1 + sqrt(5.0)) / 2.0; // 黄金分割数 int Wythoff(int a, int b) { if (a > b)

hdu 2551 竹青遍野

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2551 hint:就是读懂题就行了 #include <iostream> #include <cstdio> using namespace std; typedef long long LL; LL data[1005]; int main() { data[0]=0; for(int i=1; i<1005; i++) data[i]+=data[i-1]+i*i*i; LL

hdu 2054 A == B?

http://acm.hdu.edu.cn/showproblem.php?pid=2054 此题巨坑,刚开始我以为是简单的水题,就用strcmp过, but错了,后来经过我苦思冥想,结果还有几组数据 0.0 和 0,1.000和1.0 , 但是我不太确定前面的0是不是有作用我还是写了,但是有人过的时候,前面的0没考虑比如: 002和2可能是相等的,也可能是不想等的所以不用判断,只能说明hdu数据不是很强啊,嘿嘿 代码如下: #include <iostream> #include <c

hdu 4430 Yukari&#039;s Birthday

点击打开链接hdu 4430 思路:枚举r+二分k 分析: 1 题目要求的是找到一组最小的r*k,如果r*k相同那么就找r最小的. 2 很明显k>=2,根据n <= 10^12,那么可以知道r的最大值r<50,所以只要枚举枚举r的值,然后二分k的大小找到所有的解,存入一个结构体里面,然后在对结构体排序,那么这样就可以得到最后的ans 3 注意题目说了中心点最多一个蜡烛,所以写二分的时候应该注意判断的条件: 4 还有可能计算得到结果超了long long直接变成负数所以应该对或则个进行判断

hdu 1238 Substrings

点击打开链接hdu 1238 思路:kmp+暴力枚举子串 分析: 1 题目要求找到一个子串x,满足x或x的逆串是输入的n个字符串的子串,求最大的x,输出x的长度 2 题目的n最大100,每一个字符串的最大长度为100,那么暴力枚举子串就是o(n^2)才10000肯定是不会超时的,但是由于这里涉及到了逆串的问题,所以我们应该还要求出n个子串的逆串,然后在求最大的x. 代码: #include<iostream> #include<algorithm> #include<cstd

hdu 1857 Word Puzzle

点击打开链接hdu 1857 思路:字典树 分析: 1 题目要求的是给定的单词第一个字母在这个矩形里面的最小的坐标 2 矩形的最大500*500,单词的来源有三个方向,并且单词的起点和终点在矩形之内都是可能的.所以的如果利用枚举矩形之内的单词,那么肯定是超内存的 3 所以我们必须考虑另一种的方法就是对单词进行建字典树,那么我们只要去枚举单词的可能的起点,然后进行查找相应的单词是不是在树上,如果是的话就标记一下当前的坐标. 4 注意由于单词的来源有三个方向,但是因为要求的如果下相同的情况下要求坐标