Bone Collector II
time limit per test 1 second memory limit per test 256 megabytes
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.

传送门:HDU2639

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

1
2
3
4
5
6
7
8
9
10
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

1
2
3
12
2
0

题解

背包第K大入门题 怎么求第K大那 首先理解一个思想 如果分成好几堆 那么第K大应该是这几堆中前K大的一个 那么我们在做dp时应该多开一维记录当前的前K大,那么后面的前K大是基于前面前K大和自己当前的前K大合并的一个有序数组的前K大.
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
while(sc.hasNext()){
int n=sc.nextInt();
int v=sc.nextInt();
int k=sc.nextInt();
int[]val=new int[n];
int[]cost=new int[n];
int[]A=new int[k+2];
int[]B=new int[k+2];
for(int i=0;i<n;i++){
val[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
cost[i]=sc.nextInt();
}
int[][]dp=new int[v+1][k+2];
for(int i=0;i<n;i++){
for(int j=v;j>=cost[i];j--){
int kk=0;
for(kk=1;kk<=k;kk++){
A[kk]=dp[j-cost[i]][kk]+val[i];
B[kk]=dp[j][kk];
}
A[kk]=B[kk]=-1;
int a=1;
int b=1;
int c=1;
while(c<=k && (A[a]!=-1 || B[b]!=-1)) {
if(A[a]>B[b]){
dp[j][c]=A[a];
a++;
}
else{
dp[j][c]=B[b];
b++;
}
if(dp[j][c]!=dp[j][c-1])
++c;
}
}
}
pw.println(dp[v][k]);
pw.flush();
}

}
}