完全背包
前置知识:01背包点击我跳转喵!
概念:完全背包相对于01背包,完全背包是物品数量无限的背包,也就是说,一个物品,我们想要拿多少拿多少(只要背包装得下)。
这就很不一样了,我们具体来看看 $\tt DP$ 怎么推。
思路:构建 $\tt DP$想要让数量无限,我们可以同样设置和 $01$ 背包一样的状态,也就是:
12dp[i][j];// 表示:前 i 个物品里选择出体积为 j 的最大价值
那么问题就是,如何在这个的基础上,做到每一个物品选好多次。
题外话:一个粗劣的算法
所谓数量无限其实只是你背包装不下,也就是说,从某种意义上来讲,我们可以在加一层循环,枚举某一个物品买了几次的01背包。
1234for(int i = 1; i <= n; i++) // 枚举物品 for(int j = 0; j <= v; j++) // 枚举体积 for(int k = 0; k * c[i] <= j; k++) // 三重循环 枚举每种取用件数*c[i]不大于当前总体积j dp[i][j] = max(dp[i][j], dp ...
01背包
概念:什么是01背包01背包,顾名思义,每一个项不是 $0$ 就是 $1$ 的背包。显而易见,就是选和不选的背包。
那就是说,这是一个每个物品只有一个,且只能选货不选得出最大价值的背包问题
证明:怎么做01背包先来看看这道题,显而易见有两种可能,一是贪心,二是 $\tt DP$。那么是哪一种呢?不用想太多,我们可以感性理解。
假设你在买东西,对于一样的物品,你怎么选?肯定是选性价比高的啊!性价比就是性能和价格的比值,体现在这个题目中,他给我们造成的收益是性能,也就是购买这个物品的价值;我们选择它花费的代价是价格,也就是体积。
所以如果要贪心,一种方法就是按照性价比排序,所以说我们或许只需要出一个数据卡掉他,他就是DP题了。
1234570 3 // 背包体积 物品数量// 物品体积 物品价值60 600 // 性价比:1020 180 // 性价比:950 430 // 性价比:8.6
按照贪心的方法,他选了 $60$ 就不可以再次选了,但是我们知道最优解是选 $20 + 50$ 。这也告诉我们这是一道 $\tt DP$ 而非贪心。
推导:如何设计01背包首先从最简单的开始 ...
HDU4597 拾牌游戏
题面大秦为你打开题目传送门
题目描述两人轮流从两堆牌中抽取最顶端或者最底部的牌,得到的分数加到自己身上,假设两个人都绝顶聪明,两个人都想让自己的得分最大,问先拿牌的最多能得多少分。
题解首先拿到这道题,要考虑怎么设置状态。
首先,想要记录当前排队状态,因为 $n$ 特别小,所以只需要直接开 $dp[l1][r1][l2][r2]$ 分别表示两个数组被取成这样的方案就可以了。但是还有一个问题就是要不要分开讨论两个人。
显然不用,因为题目给出要求 “假设两个人都绝顶聪明” 所以每个人都走最优方案就可以了。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>using namespace std;int n;int a[25], b[25];int sum;int dp[25][25][25][25];void Input() { scanf("%d", &n ...
树的重心
树的重心的概念如果在树中选择某个节点并删除,这棵树将分为若干棵子树,统计子树节点数并记录最大值。取遍树上所有节点,使此最大值取到最小的节点被称为整个树的重心。
说白了就是删去一个点,使这一颗树碎成的块块大小最平均的那一个点,就是重心。
树的重心的代码我们只需要把每一个子树的大小都处理出来,在该节点的父亲方向的点可以用总量减去所有的儿子方向的子树。处理出所有子树的最大值,按照定义模拟即可。
值得注意的是,一个树可以有多个重心,但是他们一定相邻。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;int n;vector<int >e[10010];int size[10010];int g[10010];void Input(){ scanf("%d", &n); int u, v; for(int i= ...
并查集
需求:问题需要问题$\tt A$ 是 $\tt B$ 的亲戚,$\tt B$ 是 $\tt C$ 的亲戚,那么 $\tt A$ 是 $\tt C$ 的亲戚,给出若干个这样的关系,问某两个人是亲戚吗?
思考想要实现这样的关系,我们可以先不往算法的方向想,我们可以想如果这是小学数学题你怎么办,考虑如下几种情况:
这样就是我们要说的并查集的基本原理了,只不过写成代码还有亿点点路程,让我们继续推
想要实现这样的功能我们为什么不用 $\tt set$ 集合呢,似乎比我们想要的还要更加直观。当然不行,$\tt set$ 的本质也是树啊(,而且如果我在这个并查集上面要带权值呢(
所以我们这就是要用树形结构,思路也很好懂,比如说我这个 $\tt A$ 是 $\tt B$ 的亲戚,我就可以把 $\tt A$ 的父亲设为 $\tt B$ 这样的操作。
概念 并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。
编写:实现思想基础思路用刚刚的思路就可以写出如下代码:
12345int fa[N];int find(int x) { ...
树的直径
概念:什么是树的直径树上距离最远的两个点所连接的路径,叫做树的直径,显而易见的,一个树可以有多个直径。
实现:怎么写树的直径Dfs深搜两遍思路很简单,直接去找最远的两个点。先从任意点开始,找到距离他最远的点,记作 $x$ ;然后从 $x$ 开始找最远的点,记作 $y$ 。$x$ 和 $y$ 连接后的路径就是直径。但是这种深搜的做法无法解决负边权的树。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<bits/stdc++.h>using namespace std;int n;vector<pair<int , int > >e[30010];int dis[30010], vis[30010];void Input(){ scanf("%d", &n); int u, v, w; for(int i=1; i<n; i++){ scanf(& ...
USACO 进击的奶牛
题面大秦为你打开题目传送门
题目描述Farmer John 建造了一个有 $N$($2 \leq N \leq 10 ^ 5$) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是 $x _ 1, x _ 2, \cdots, x _ N$($0 \leq x _ i \leq 10 ^ 9$)。
他的 $C$($2 \leq C \leq N$)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John 想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?
输入格式第 $1$ 行:两个用空格隔开的数字 $N$ 和 $C$。
第 $2 \sim N+1$ 行:每行一个整数,表示每个隔间的坐标。
输出格式输出只有一行,即相邻两头牛最大的最近距离。
样例 #1样例输入 #11234565 312849
样例输出 #113
题意在坐标轴上有 n 个点,从中选取 m 个点,使得这m个点两两之间的最小距离最大。
看到使最小什么什么最大,直接二分,二分最小距离,$\tt Check$ 函数直接 $O(n) ...
POJ3685 Matrix
题面大秦为你打开题目传送门 (看不懂就看下面吧)
有一个$N× N$ 的矩阵
第 $i$ 行第 $j$ 列的值为 $𝑖^2 +100000× 𝑖 + 𝑗^2 −100000× 𝑗 + 𝑖 × 𝑗$
求矩阵中第 $M$ 小的数。
题意二分第 $M$ 小的数,然后 $check$ 时枚举 $i$ ,再二分找小于 $mid$ 的数字,加起来看看是不是 $M$
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include<bits/stdc++.h>using namespace std;typedef long long ll;int n;ll m;void Input(){ scanf("%d%lld", &n, &m);}ll Calc(ll i, ll j, ll x){ if(i==n+1) return max(x, ...
517七段第四课D
题面大秦为你打开题目传送门 (看不了的就看下面吧)
找出最小的自然数据 $N$ ,使得 $N!$ 刚好有 $Q$ 个后缀零。$N!=1\times2\times…\times N$ 例如 $5!=1\times2\times3\times4\times 5=120$, $120$有 $1$ 个后缀 $0$ 。
题意显而易见的,$N$ 越大,阶乘的后缀零越多,所以这是一个二分题。
二分答案 $N$ ,对于它数 $1$ 至 $N$ 有几个因子 $5$ 。显然,$1$ 至 $N$ 中 $5$ 的倍数是 $\lfloor N/5\rfloor$ 但是,这还不够,因为有一些数字有多个因数 $5$ 。所以要把那些 $5$ 的倍数拿出来反复如上操作,如下图。
我们设 $N = 30$ ,然后做第一个除以 $5$ 的操作,答案是 $6$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N
N
N
N
Y
N
N
N
N
Y
N
N
N
N
Y
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
N
N
N
N
Y ...
517七段第四课B
题面大秦为你打开题目传送门 (看不了的就看下面吧)
看下图
已知三角形 $ABC$ ,$DE$ 平行于 $BC$ ,给定三角形 $ADE$ 与四边形 $BCED$ 的面积之比,求 $AD$ 的长度。
题意显而易见的,使用相似,这道题可以用数学方法 $O(1)$ 求解。三分的话我们可以直接三分答案拿着算出的答案就去和比例比,就可以了。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<bits/stdc++.h>using namespace std;const double eps = 1e-10;double AB, AC, BC, k;void Input() { scanf("%lf%lf%lf%lf", &AB, &AC, &BC, &k); // cout<<AB<<AC<<BC<<k& ...