HDU 2639 01背包求第k大
2024-08-30 20:39:50
Bone Collector II
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3718 Accepted Submission(s): 1903
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.
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
Author
teddy
Source
题意:2602的改版 与普通01背包不同是求第k大价值
题解:增加一维 存储 dp[i][w] 容量为i的背包存放的物品的第w大价值和
增加一步 两个序列合并的过程 形成新的k大
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#define ll __int64
#define pi acos(-1.0)
#define mod 1
#define maxn 10000
using namespace std;
int t;
int n,v,k;
int a[];
int b[];
int we[],va[];
int dp[][];
int main()
{
while(scanf("%d",&t)!=EOF)
{
for(int i=;i<=t;i++)
{
memset(we,,sizeof(we));
memset(va,,sizeof(va));
memset(dp,,sizeof(dp));
scanf("%d %d %d",&n,&v,&k);
for(int j=;j<=n;j++)
scanf("%d",&we[j]);
for(int j=;j<=n;j++)
scanf("%d",&va[j]);
for(int j=;j<=n;j++)
{
for(int l=v;l>=va[j];l--)
{
memset(a,,sizeof(a));
memset(b,,sizeof(b));
for(int m=;m<=k;m++)
{
a[m]=dp[l][m];
b[m]=dp[l-va[j]][m]+we[j];
}
a[k+]=-;
b[k+]=-;
int x=,y=,w=;
while(w<=k&&(x<=k||y<=k))//合并的过程
{
if(a[x]>b[y])
{
dp[l][w]=a[x];
x++;
}
else
{
dp[l][w]=b[y];
y++;
}
if(w==||dp[l][w]!=dp[l][w-])
w++;
}
}
}
cout<<dp[v][k]<<endl;
}
}
return ;
}
最新文章
- node如何让一个端口同时支持https与http
- 基于spring的文件上传--单文件上传
- 【C语言入门教程】5.2 函数的作用域规则(auto, static)
- (转) C/C++中const关键字详解
- emoji表情引发的JNI崩溃
- 学习jQuery的事件dblclick
- Android学习系列(15)--App列表之游标ListView(索引ListView)
- 网络基础知识HTTP(1) --转载
- React 基础入门
- LeetCode算法题-Search in a Binary Search Tree(Java实现)
- request.getParameter()获取不到数据
- Tomcat入门
- Python自动化开发 - 常用模块(二)
- 微信小程序的wx-charts插件
- npm发布插件步骤
- Delphi的idhttp报IOHandler value is not valid错误的原因
- feginclient demo
- 京东7Fresh新零售架构设计分析
- Educational Codeforces Round 12 C. Simple Strings 贪心
- IOS实现打电话后回调