hdu 2639 Bone Collector II 第k大01背包

题目链接

题意：求第k大的01背包。

每次比较时保存前k大的情况。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 1100

using namespace std;

int d[N][N],v[N],w[N],a[N],b[N];

int main()
{
    int T,n,m,K;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>K;
        for(int i=0;i<n;i++)    scanf("%d",&v[i]);
        for(int i=0;i<n;i++)    scanf("%d",&w[i]);
        memset(d,0,sizeof(d));
        for(int i=0;i<n;i++)
            for(int j=m;j>=w[i];j--)
            {
                for(int k=1;k<=K;k++)
                {
                    a[k]=d[j][k];
                    b[k]=d[j-w[i]][k]+v[i];
                }
                int x=1,y=1,z=1;
                a[K+1]=b[K+1]=-1;
                while(z<=K&&(x<=K||y<=K))
                {
                    if(a[x]>b[y])   d[j][z]=a[x++];
                        else    d[j][z]=b[y++];
                    if(d[j][z]!=d[j][z-1])  z++;
                }
            }
        cout<<d[m][K]<<endl;
    }
}