题目描述
Bone Collector II
解法：0-1背包的第K优解
#include <iostream>
#include <algorithm>
#include<functional>using namespace std;int tt, nn, vv, kk;
int val[1008];
int vol[1008];int main()
{
cin >> tt;while(tt--){
int dp[1008][38] = {
0};cin >> nn >> vv >>kk;for(int i=0;i<nn;i++) cin >> val[i];for(int i=0;i<nn;i++) cin >> vol[i];for(int i=0;i<nn;i++){
for(int j=vv;j>=vol[i];j--){
int tmp[70] = {
0};int cnt = 0;for(int k=0;k<kk;k++){
tmp[cnt++] = dp[j][k];tmp[cnt++] = dp[j-vol[i]][k]+val[i];}sort(tmp, tmp+cnt, greater<int>());// 不能直接用nth_element，因为要去重int* p = unique(tmp, tmp+cnt);while(p != tmp+cnt){
*p = 0;p++;}copy(tmp, tmp+kk, dp[j]);}}cout << dp[vv][kk-1] << endl;}return 0;
}