HDU 2639(01背包第K大)

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

http://blog.csdn.net/lulipeng_cpp/article/details/7584981

求第K大的思路是把每个d[v]看成是由d[v]和d[v-cost]+weight两个序列组成的，然后分别记录每个序列的第k大，然后逐项更新。

用个形象的比喻吧：如果我想知道学年最高分，那么，我只要知道每个班级的最高分，然后统计一遍就可以了。

如果我想知道学年前十呢？我必须要知道每个班的前十名。大家在心里模拟一下，对，这就是本题核心的算法。两种决策，就可以看作这个学年只有两个班。

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

using namespace std;

#define MEM(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define debug printf("!/n")

#define INF 1000

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

int dp[INF][];

int ci[INF];

int wi[INF];

int A[];

int B[];

int main()

{

          int n,V,i,j,v,t,K,k;

          sf("%d",&t);

          while(t--)

          {

                    sf("%d%d%d",&n,&V,&K);

                    MEM(dp,);

                    MEM(ci,);

                    MEM(wi,);

                    MEM(A,);

                    MEM(B,);

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

                    {

                              sf("%d",&wi[i]);

                    }

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

                    {

                              sf("%d",&ci[i]);

                    }

                    int a,b,c;

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

                    {

                              for(v = V;v>=ci[i];v--)

                              {

                                        for(k = ;k<=K;k++)

                                        {

                                                  A[k] = dp[v][k];

                                                  B[k] = dp[v-ci[i]][k]+wi[i];

                                        }

                                        A[K+] = B[K+] = -;

                                        a = b = c = ;

                                        while(c<=K && (A[a] != - || B[b] != -))

                                        {

                                                  if(A[a]>B[b])

                                                  {

                                                            dp[v][c] = A[a];

                                                            ++a;

                                                  }

                                                  else

                                                  {

                                                            dp[v][c] = B[b];

                                                            ++b;

                                                  }

                                                  if(dp[v][c] != dp[v][c-])

                                                            ++c;

                                        }

                              }

                    }

                    pf("%d\n",dp[V][K]);

          }

    return ;

}