Charlesss
Charlesss
全部文章
分类
ACM_RMQ(2)
ACM_二分(5)
ACM_二分图(8)
ACM_前缀和(1)
ACM_动态规划(18)
ACM_干货(6)
ACM_并查集(3)
ACM_拓扑排序(2)
ACM_搜索(24)
ACM_最短路(14)
ACM_树(1)
ACM_树状数组(2)
ACM_生成树(8)
ACM_线段树(3)
ACM_覆盖问题(2)
ACM_连通图(2)
CodeForces(131)
未归档(172)
第九届蓝桥杯(2)
算法(3)
补题补题补题(55)
题解(3)
归档
标签
去牛客网
登录
/
注册
Charlesss的博客
全部文章
(共467篇)
HDU 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重背包裸题)
一道多重背包的裸题,想看详解的可以看这篇博客传送门(Coins) AC代码: #include <iostream> #include <cstring> #define MAX(a,b) a>b?a:b #define MAXN 100000...
2018-02-10
0
507
HDU 2844 Coins (多重背包+二进制优化)
首先这是一道多重背包的裸题,题意在代码中的注释里有。多重背包就是所给的物品是有限的(任意个),我们则可以把多重背包的问题转换成01背包和完全背包来求解。首先我们先把01背包和多重背包的过程封装成函数,需要用的时候传参过去就好了,然后我来解释一下什么时候用01背包,什么时候用完全背包。我...
2018-02-10
0
303
NYOJ 311 完全背包(恰好装满)
就直接上代码吧,至于判断恰好装满问题可以看下这篇博客传送门(Piggy-Bank) 需要注意的是直接调用max函数会TLE,所以以后还是不要懒省事的直接调用max函数吧。 AC代码: #include <iostream> #include <cstring> #inclu...
2018-02-10
0
374
POJ 2603 HDU 1963 Investment(完全背包)
这有一篇完全背包的详解,也加了判断是否恰好装满的状态传送门(Piggy-Bank) 题意在代码注释中有,算是完全背包的模板题吧,但是需要注意一点,因为题目中说了所有数据都是1000的倍数,所以我们可以对数据都进行缩小1000倍来进行计算。 AC代码: #include...
2018-02-10
0
337
HDU 1114 Piggy-Bank(完全背包+恰好装满)
就以这道题来简单讲解一下完全背包问题,首先完全背包和01背包的区别在于01背包每样物品只有一个,用完了就不能再用了,而完全背包的物品是有无限个的,所以完全背包又衍生出能不能把背包恰好装满的问题。能否恰好装满问题对dp数组初始化的时候做点改变就行了。 下面是完全背包的核心...
2018-02-10
0
353
NYOJ 860 又见01背包(思维)
刚一看这道题以为是01背包的裸题,TLE了一次后发现这是一道拐了个弯的裸题,题中给的物品重量范围太大了,所以我们可以换种思路,把最大价值求出来,然后在dp中用价值去存重量,然后价值从大到小遍历找出第一个不大于题中给的重量,然后输出价值即可。 AC代码: #include <i...
2018-02-08
0
348
HDU 2546 饭卡(01背包+预处理)
这是一道01背包问题,但是需要预处理一下,因为当你的钱不够5块钱的时候,你什么都买不了,所以直接输出钱数,当你的钱大于5块钱的时候,你可以先拿出来5块钱,留着最后去买最贵的菜,现在你剩下m-5块钱,排个序把最贵的留在最后,然后就用01背包把这m-5尽量装满(遍历1~n-1种菜,因为n是...
2018-02-08
0
353
HDU 1171 Big Event in HDU(01背包)
题意在代码注释中有,思路就是先记录所有价值的总和sum,既然要求两个学院分得的器材价值尽量接近,那么取总和的一半ans,让其中一个学院尽量接近ans,那么另一个学院也会尽量接近ans,所以就两个学院尽量相同了。还有就是器材可能不唯一,所以需要再加一个for循环把这个器材用完。 AC代...
2018-02-08
0
303
HDU 2955 Robberies(01背包+思维)
这是一道关于小数的01背包问题,题意代码注释中有,如果按着题的思路来写,会发现那个概率是小数,在转移方程里没法实现,所以我们需要换个方向思考了。我们可以按成功逃跑的概率来算,每个w数组里存成功逃跑的概率,然后让总价值作为背包容量,然后在dp中用价值去存逃跑的概率,最后从价值最大(背包容...
2018-02-08
0
621
POJ 3624 Charm Bracelet(01背包模板题)
又是一道01背包裸题。 AC代码: #include <iostream> #include <cstring> #include <cstdio> #define MAX(a,b) a>b?a:b using namespace std;...
2018-02-08
0
304
首页
上一页
38
39
40
41
42
43
44
45
46
47
下一页
末页