luogu 1858

代码

//背包第K优解
//中间添加合并过程
//背包九讲
#include <cstdio>
#include <cstring>
using namespace std;
int f[5001][51];
int k,v,n;
int t[51];

int main(){
    memset(f,0xcf,sizeof(f));
    f[0][1] = 1;
    scanf("%d%d%d",&k,&v,&n);

    f[0][1] = 0;
    int a,b;
    for(int i =1;i<=n;i++){
        scanf("%d%d",&a,&b);
        for(int j=v;j>=a;j--){
            if(f[j-a][1]>=0){
                int p1 = 1,p2 = 1;
                for(int u=1;u<=k;u++){
                    t[u] = f[j][u];
                    if(f[j-a][p2] + b > t[p1])
                        f[j][u] = f[j-a][p2++]+b;
                    else
                        f[j][u] = t[p1++];
                }
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=k;i++){
        ans+=f[v][i];
    }
    printf("%d\n",ans);

    return 0;
}