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("
")
#define LL long long

int dp[INF][50];

int ci[INF];
int wi[INF];

int A[50];
int B[50];


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,0);
                    MEM(ci,0);
                    MEM(wi,0);
                    MEM(A,0);
                    MEM(B,0);

                    for(i = 1;i<=n;i++)
                    {
                              sf("%d",&wi[i]);
                    }

                    for(i = 1;i<=n;i++)
                    {
                              sf("%d",&ci[i]);
                    }

                    int a,b,c;

                    for(i = 1;i<=n;i++)
                    {
                              for(v = V;v>=ci[i];v--)
                              {
                                        for(k = 1;k<=K;k++)
                                        {
                                                  A[k] = dp[v][k];
                                                  B[k] = dp[v-ci[i]][k]+wi[i];
                                        }

                                        A[K+1] = B[K+1] = -1;
                                        a = b = c = 1;

                                        while(c<=K && (A[a] != -1 || B[b] != -1))
                                        {
                                                  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-1])
                                                            ++c;
                                        }
                              }
                    }

                    pf("%d
",dp[V][K]);
          }
    return 0;
}