HDU - 2639 Bone Collector II (01背包第k大解)

分析

\(dp[i][j][k]\)为枚举到前i个物品,容量为j的第k大解.则每一次状态转移都要对所有解进行排序选取前第k大的解.用两个数组\(vz1[],vz2[]\)分别记录所有的选择情况,并选择其中前k大的更新当前的dp[i][k].因为dp[i]满足递增的特点,所以可以对两个数组顺序比较选择.

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3+5;

const int INF = 0x3f3f3f3f;

int dp[maxn][maxn];

int v[maxn], w[maxn];

int vz1[maxn], vz2[maxn];

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt", "r", stdin);

        freopen("out.txt", "w", stdout);

    #endif

    int T;

    scanf("%d",&T);

    while(T--){

        int n,W,k;

        scanf("%d %d %d",&n, &W, &k);

        for( int i = 1;i <= n; ++i)

            scanf("%d",&v[i]);

        for(int i=1;i<=n; ++i)

            scanf("%d",&w[i]);

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n; ++i){

            for(int j = W; j>= w[i]; --j){

                for(int t = 0;t < k;++ t){

                    vz1[t] = dp[j][t];

                    vz2[t] = dp[j-w[i]][t] + v[i];

                }

                vz1[k]= vz2[k] = -1;

                for(int x = 0, y = 0, z = 0 ;(x < k || y < k) && z < k ; ){

                    if( vz1[x] > vz2[y] )

                        dp[j][z] = vz1[x++];

                    else

                        dp[j][z] = vz2[y++];

                    if( z == 0 || dp[j][z-1] != dp[j][z])

                        z++;

                }

            }

        }

        printf("%d\n", dp[W][k-1]);

    }

    return 0;

}