Hdu 2639 Bone Collector II

本文主要是介绍Hdu 2639 Bone Collector II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求价值第K大的01背包问题，技巧是多加一维表示第k大时的价值，转移的时候用两个有序数列合并的方法不断更新第二维。

/********************* Author:fisty* Data:2014-11-6* HDU2639* *****************/#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N 1000
int dp[MAX_N][MAX_N];
int w[MAX_N], v[MAX_N];
int N, V, K;void solve(){int a[MAX_N], b[MAX_N];memset(dp, 0, sizeof(dp));for(int i = 0;i < N; i++){for(int j = V; j >= v[i]; j--){int p = 0, q = 0;for(int k = 1;k <= K; k++){b[q++] = dp[j][k];a[p++] = dp[j-v[i]][k]+w[i];}//mergeint x = 0, y = 0, k = 1;while(k <= K && (x < p || y < q)){int t = 0;if(y >= q || x < p && a[x] > b[y]){t = a[x++];}else{t = b[y++];}if(k == 1 || t != dp[j][k-1]){dp[j][k++] = t;       }}}       }printf("%d\n", dp[V][K]);
}
int main(){int t;scanf("%d", &t);while(t--){scanf("%d%d%d", &N, &V, &K);for(int i = 0;i < N; i++){scanf("%d", &w[i]);       }for(int i = 0;i < N; i++){scanf("%d", &v[i]);}solve();}return 0;
}

这篇关于Hdu 2639 Bone Collector II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---