vijos1412(第k优背包)

求第Ｋ优的背包．然后选前Ｋ大的价值求和

/*************************************************************************
	> File Name: vijos1059.cpp
	> Author: 
	> Mail: 
	> Created Time: 2017年10月16日 星期一 10时33分45秒
 ************************************************************************/
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#define maxn 5010  
#define INF 0x3f3f3f3f  
using namespace std;  
int dp[maxn][55];  
int f[55],a[maxn],b[maxn];  
int k,v,n;  
int x,y,z;  
int main()  {  
    scanf("%d%d%d",&k,&v,&n);  
    for(int i=0; i<=v; i++) fill(dp[i],dp[i]+k+2,-INF);  
    dp[0][1]=0;  
    for(int i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]);  
    for(int i=0; i<n; i++)  
    {  
        for(int j=v; j>=a[i]; j--)  
        {  
            if(dp[j-a[i]][1]!=-INF)  
            {  
                x=y=z=1;  
                for(;z<=k;z++)  //把原来的包全部取出，跟新的包比较，拿出最大的50个包存起来；  
                {  
                    f[z]=dp[j][z];  
                    if(dp[j-a[i]][y]+b[i]>f[x])  
                    {  
                        dp[j][z]=dp[j-a[i]][y]+b[i];  
                        y++;  
                    }  
                    else  
                    {  
                        dp[j][z]=f[x];  
                        x++;  
                    }  
                }  
            }  
        }  
    }  
    int ans=0;  
    for(int i=1; i<=k; i++)  
    {  
        ans+=dp[v][i];  
    }  
    printf("%d\n",ans);  
    return 0;  
}