动态规划
定义及分类
多阶段决策过程的最优化问题。动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
Code实例01Bag题目
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为$W_1$，$W_2$至$W_n$，与之相对应的价值为$P_1$,$P_2$至$P_n$。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。求解将哪些物品装入背包可使价值总和最大。
主要思路每一个物品有2种状态:不装(0)和装(1)，将其分解后的最终问题是能不能放进这个物品?我们可以构建如下表格每一栏表示在当前最大重量和物品数的时候的最大价值最大重量:10重量:{2,2,6,5,4}价值:{6,3,5,4,6}以如上数据为例，根据状态转移方程，可构建如下表格。
物品数\质量
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
6
6
6
6
6
6
6
6
6
2
0
0
6
6
9
9
9
9
9
9
9
3
0
0
6
6
9
9
...
广度优先搜索
BFS主要思想将全部邻接点入队列，以FIFO原则，依次访问所有未访问节点
模版题及其实现最小花费
在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
输入格式
第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
输出格式
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
样例输入
3 31 2 12 3 21 3 31 3
样例输出
103.07153164
数据范围及时空限制
1<=n<=20001000ms40960kb
代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 ...
二叉树的遍历
二叉树
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树的定义和结构1234567struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};
以存储int值为数据的二叉树为例,每一个二叉树节点有一个左节点和右节点,故以此建立树节点的结构体,初识孩子指针为NULL。
二叉树从前序和中序遍历建树主要思想 A
/ \
B C
/ \
D E
如上二叉树:前序遍历为 ABDEC中序遍历为 DBEAC
不难发现，在这两种遍历中，以前序遍历的顺序在中序遍历中寻找对应节点。在找到该节点后，其中序遍历左侧的即为左子树，右侧即为右子树。
原理讲解Step 1:ABDECDBEAC
目前的树：
A
=>根节点是A，现在考虑左子树St ...
线段树
线段树的作用
线段树是一种二叉搜索树,它能以较低时间复杂度O(logN)得解决大规模求和、gcd等空间复杂度为2N，但实际应用时还需4N的空间
查询和单点更改的代码实现123456789101112131415class NumArray{ public: int *tree; int size; NumArray(vector<int> nums) { size = nums.size(); //size储存原始数据的数量 tree = new int[size * 4]; if (size != 0) Build(1, size, 1, nums); //以1为根节点，为了防止计算问题而废除0号位置 }
线段树大小为原始数组大小的4倍
==>Q:树叶节点和树节点一共2n个数据，为什么需要4倍?==>A:在递归时候仍然需要访问叶子节点下一层子树，下一层子节点一共有2n个，所以共计4n的空间需求
1 ...
First-blog
First Blog
FormatsTestingTestingtesting
Hyperlink行内形式: Github自动链接: Github http://github.com/GZTimeHacker
List
first item
second item
third item
Table
表头1
表头2
表头3
表头4
默认左对齐
左对齐
居中对其
右对齐
默认左对齐
左对齐
居中对其
右对齐
默认左对齐
左对齐
居中对其
右对齐
Code1234567#include<iostream>using namespace std;int main(){ cout<<"hello world"; return 0;}
Mathjax
空心的符号：\mathbb{KL} $\mathbb{KL}$
向量、矩阵：\mathrm{x, y} $\mathrm{x, y}$
实值：x $x$
根式：\sqrt[x]{y} $\sqrt[x]{y}$
常见的三角函数，如 $ ...
问
5e15dcdb3bbbdb8d74e8dcafcadae52530b6b8f271318fd724817cb4e9b31b054a68d85ee4907e7862cc9ca265535a088c9aa01e3ad2fdaf2f437b9c4470806fb04a6ff796ca222cfea0846dad925f8049e2ed2875f50b0d0ff09d57a13aec6059838addd6ba0f8d37b9222059323013ef6598c9419ef17c96ab0ade1a127e20313d9f8f4d33aba26994cbf5d633dda1c332ce656166bbc02c963eb336dae85b420c1b64dc0a44c35a3bfe50b12c425fbdf7329968365e22825b1a0b2d2a6d40db42626afb47e6f7b6cd2f97a4f7fa5bf61363b06daf4fd9c2ce3eb68d736708026fa9a1af3ee05e68d7eabd1bdfc93372ac3df19c88bfa72 ...