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;
}
全部评论

相关推荐

06-04 18:37
门头沟学院 Java
勇敢的ssr求对象:前面看的有点奔溃,看到只有你是真玩啊,忍不住笑出了声😂
点赞 评论 收藏
分享
LemontreeN:有的兄弟有的我今天一天面了五场,4个二面一个hr面
投递字节跳动等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务