hdu 2639 Bone Collector II

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2639

思路：01背包 第K优解

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>
using namespace std;
int N,V,K;
int f[1010][35];
int A[35],B[35];
int v[110],w[110];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&N,&V,&K);
        for(int i=1;i<=N;i++)
            scanf("%d",&v[i]);
        for(int i=1;i<=N;i++)
            scanf("%d",&w[i]);
        memset(f,0,sizeof(f));
        int k;
        for(int i=1;i<=N;i++)
            for(int j=V;j>=w[i];j--)
            {
                for(k=1;k<=K;k++)
                {
                    A[k]=f[j][k];
                    B[k]=f[j-w[i]][k]+v[i];
                }
                A[k]=-1,B[k]=-1;
                int a=1,b=1,c=1;
                while(c<=K&&(A[a]!=-1||B[b]!=-1))
                {
                    if(A[a]>B[b])
                        f[j][c]=A[a],a++;
                    else
                        f[j][c]=B[b],b++;
                    if(f[j][c]!=f[j][c-1])
                        c++;
                }
            }
            printf("%d
",f[V][K]);
    }
    return 0;
}