Charlesss

ACM_动态规划

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) 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)

/ 注册

全部文章 / ACM_动态规划（共18篇）

NYOJ 18 The Triangle

动态规划问题，题意是输入一个数字三角形，然后从上往下走一条路，问走到底端的最大值。如果从上往下走的话会有很多种情况，所以不如反过来从下往上递推，比较大小求最大值。 AC代码： #include <iostream> #include <cstdio> #def...

2018-03-06

0 377

POJ 2603 HDU 1963 Investment(完全背包)

这有一篇完全背包的详解，也加了判断是否恰好装满的状态传送门(Piggy-Bank) 题意在代码注释中有，算是完全背包的模板题吧，但是需要注意一点，因为题目中说了所有数据都是1000的倍数，所以我们可以对数据都进行缩小1000倍来进行计算。 AC代码： #include...

2018-02-10

0 404

NYOJ 860 又见01背包(思维)

刚一看这道题以为是01背包的裸题，TLE了一次后发现这是一道拐了个弯的裸题，题中给的物品重量范围太大了，所以我们可以换种思路，把最大价值求出来，然后在dp中用价值去存重量，然后价值从大到小遍历找出第一个不大于题中给的重量，然后输出价值即可。 AC代码： #include <i...

2018-02-08

0 415

HDU 1171 Big Event in HDU(01背包)

题意在代码注释中有，思路就是先记录所有价值的总和sum，既然要求两个学院分得的器材价值尽量接近，那么取总和的一半ans，让其中一个学院尽量接近ans，那么另一个学院也会尽量接近ans，所以就两个学院尽量相同了。还有就是器材可能不唯一，所以需要再加一个for循环把这个器材用完。 AC代...

2018-02-08

0 371

HDU 2955 Robberies(01背包+思维)

这是一道关于小数的01背包问题，题意代码注释中有，如果按着题的思路来写，会发现那个概率是小数，在转移方程里没法实现，所以我们需要换个方向思考了。我们可以按成功逃跑的概率来算，每个w数组里存成功逃跑的概率，然后让总价值作为背包容量，然后在dp中用价值去存逃跑的概率，最后从价值最大(背包容...

2018-02-08

0 695

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 384

HDU 2602 Bone Collector(01背包模板题)

一道01背包的裸题，不带拐弯的裸题...看代码吧 AC代码： #include <iostream> #include <cstring> using namespace std; const int MAXN = 1005; //数组不要开太小，不然会...

2018-02-08

0 394

Hiho Coder 1038 01背包(模板)

01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi，求将哪些物品装入背包可使获得的价值总和最大。而这道题的题意也就是这个意思，01背包的特点就是每种物品仅有一件，可以选择放或者不放。下面是01背包的核心代码： for(int i = ...

2018-02-06

0 397