关键词：
01背包+归并
看的题解 https://vijos.org/p/1412/solution
#include<cstdio> #include<cstring> using namespace std; int a[205]; int b[205]; int f[5005][55]; int k,n,v; void work(int *aa,int *bb,int c) { int t[105]; int ti=1; int ai=1; int bi=1; while(ai+bi<=k+1) { if(aa[ai]>bb[bi]+c) t[ti++]=aa[ai++]; else t[ti++]=bb[bi++]+c; } for(int i=1;i<=k;i++) aa[i]=t[i]; } int main() { scanf("%d%d%d",&k,&v,&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); } for(int i=0;i<=v;i++) { for(int j=0;j<=k;j++) f[i][j]=-1e7; } f[0][1]=0; for(int i=1;i<=n;i++) { for(int j=v;j>=a[i];j--) { work(f[j],f[j-a[i]],b[i]); } } int ans=0; for(int i=1;i<=k;i++) ans+=f[v][i]; printf("%d ",ans); return 0; }
vijos107101背包+输出路径
描述过年的时候，大人们最喜欢的活动，就是打牌了。xiaomengxian不会打牌，只好坐在一边看着。这天，正当一群人打牌打得起劲的时候，突然有人喊道：“这副牌少了几张！”众人一数，果然是少了。于是这副牌的主人得... 查看详情
vijos1037背包+标记
描述2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr.F曾亲眼目睹了这次灾难。为了纪念“9?11”事件，Mr.F决定自己用水晶来搭建一座双塔。Mr.F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两... 查看详情
vijos1392拼拼图的小衫[背包dp｜二维信息dp]
背景小杉的幻想来到了经典日剧《死亡拼图》的场景里……被歹徒威胁，他正在寻找拼图（-.-干嘛幻想这么郁闷的场景……）。突然广播又响了起来，歹徒竟然又有了新的指示。小杉身为新一代的汤浅，有责任带... 查看详情
p1858多人背包(代码片段)
P1858多人背包题目描述求01背包前k优解的价值和要求装满调试日志：初始化没有赋给dp[0]Solution首先补充个知识点啊，要求装满的背包需要初始赋(-inf)，边界为(dp[0]=0)第(k)优解的01背包以(dp[j][k])表示容量为(j)的背包的第(k)优解用到... 查看详情
[洛谷p1858]多人背包
洛谷题目链接:多人背包题目描述求01背包前k优解的价值和输入输出格式输入格式：第一行三个数K、V、N接下来每行两个数，表示体积和价值输出格式：前k优解的价值和输入输出样例输入样例#1：2105312720245611输出样例#1：57说明对... 查看详情
洛谷1858多人背包
https://www.luogu.org/problem/show?pid=1858题目描述DD和好朋友们要去爬山啦！他们一共有K个人，每个人都会背一个包。这些包的容量是相同的，都是V。可以装进背包里的一共有N种物品，每种物品都有给定的体积和价值。在DD看来，合理... 查看详情
vijos1104采药
不用说了，裸的01背包。#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;inlineintread(){charc;while(c=getchar(),!isdigit(c));intx=c-‘0‘;while(c=getchar(),isdigit(c))x=x*10 查看详情
vijos1240朴素的网络游戏
...房间花费这几个信息。看到房间以及最小花费很容易想到背包dp[x]...[x]+cost[i]这种的。男生和女生我们可以看做二维费用背包，但是夫妻这个怎么处理呢。仔细想想如果有2对夫妻3对夫妻的情况我们可不可以看做2个男一个房2个女... 查看详情
急！动态规划多人背包问题
DescriptionDD和好朋友们要去爬山啦！他们一共有K个人，每个人都会背一个包。这些包的容量是相同的，都是V。可以装进背包里的一共有N种物品，每种物品都有给定的体积和价值。在DD看来，合理的背包安排方案是这样的：每个人... 查看详情
vijos1623开心农场(hoi)
...来做，最后再把钱乘以土地数量就好了。然后就是一个和背包很像的动归加个二分，在程序注释里解释好了。#include<iostream>#include<cstdio>#include<algorithm># 查看详情
luogup1858多人背包(代码片段)
gate求01背包前k优解的价值和（题面还挺亲切的）本来我想的是直接边跑01背包边记录，最后排序...然后意识到，这种方法是枚举不全的。看了眼题解...要多开一维！k的范围很小，f[i][j]表示空间为i，是第j优解。那么，因为有许... 查看详情
luogup1858多人背包(代码片段)
链接对于每个状态(f[j])多记录一个维度，转移的时候利用类似于归并排序的方法合并，以保证时间复杂度可以承受注意事项：前(K)大可以有重复的价值，法规的卫生费破口还给你#include<iostream>#include<cstring>#include<cstdio&... 查看详情
题解vijos1159岳麓山上打水(代码片段)
...要先对桶的容量从小到大排序。达到搜索层数时使用完全背包( extcheck)即可。具体实现参考代码。#include<bits/stdc++.h>#defineitnint#definegIgiusingnamespacestd;inlineintgi()intf=1,x=0;charc=getchar();while(c<'0'||c>'9')if(c=='-')f=... 查看详情
背包问题
最近，看了DD大牛的背包九讲。前面的都懂了。现在求一些题目，以及相应的标程。给的题目最好是vijos上的。0/1背包，完全背包我都掌握了。主要需要一些有依赖的背包，泛化背包等，最主要的是要有标程不管是不是官方的对... 查看详情
vijosp1426兴奋剂检查多维费用背包问题的hash
https://vijos.org/p/1426这是个好题，容易想到用dp[i][v1][v2][v3][v4][v5]表示在前i个物品中，各种东西的容量是那个的时候，能产生的最大价值。时间不会TLE,但是会MLE.所以就需要把那5维状态进行hash其实就是对这个排列进行一个hash。newSt... 查看详情
两年游戏经历
...做业务逻辑。游戏的业务逻辑大体上分两类，单人玩法和多人玩法。单人玩法例如收发邮件，背包操作，多人玩法例如组队匹配。逻辑层因为是单线程，所以做单人玩法就很简单，按照文档的逻辑实现即可，而多人玩法涉及先后... 查看详情
动态规划1(代码片段)
...bsp;-》 注意初始化（边界值）-》注意枚举顺序（完全背包第二维从小到大，01背包从大到小，区间先长度再左）LIS接上之前最优解，LCS，背包问题（01背包，完全背包，分组背包，依赖性问题）状态压缩，树形dp看过最好的一... 查看详情
vijos在vijos的自己的域中创建题目(代码片段)
创建属于自己的域https://vijos.org/填入对应信息即可。创建题目点击题库往下拉，点击创建题目进入题目之后，点击设置接下来就是重点，配置数据点：（如果想直接用，后面有捷径。）写一个正确答案... 查看详情