AKSZ-动态规划

zcc

2024-06-16 18:25:59

发布于：广东

3阅读

0回复

0点赞

图

图中顶点的度：与该顶点相连的边的数量。
在无向图中，一个顶点的度数就是和该顶点相连的边的数量。
在有向图中，一个顶点的度数等于该顶点的入度和出度的和。（入度是指指向该顶点的边的数量，出度是从该顶点出发的边的数量。）

二叉树公式推导(等比数列求和):

$\begin{aligned} f(k) = 2^0 + 2^1 + 2^2 +...+2^{(k-1)} \\ 2*f(k) = 2^1 + 2^2 + 2^3 +...+2^k\\ 2*f(k)-f(k)= 2^k -2^0 \end{aligned}$

$\begin{aligned} 2叉树公式:f(k) = 2^k -2^0 \\ a叉树公式:f(a)=(a^k-1)/(a-1);\\ 注意：节点不一定是个值 \\ \end{aligned}$

二叉树的性质

性质3：对任意一个二叉树，如果其叶子结点的数量为 $n_0$ ，度为2的结点数为 $n_2$ ，则一定满足 $n_0=n_2+1$ .
$\large具有n(n>=0)个结点的完全二叉树的深度为\lfloor log_2n+1\rfloor$
如将一棵有n个节点的完全二叉树自顶向下，同一层自左向右连续给结点编号 $\color{red}{1,2,……,n}$ ;
1. 若i=1,则结点i为根，无父结点
2. 若i>1,则i的父节点编号为 $\color{green}{ \lfloor i/2 \rfloor}$
3. 若2*i>n,则i无左孩子，否则其左孩子编号为 $2*i$ .
4. 若2*i+1>n,则i无右孩子，负责其有孩子编号为 $2 \times i+1$ .

存储方法

带权图

map[x][y]表示结点x到结点y边的权值。在边不存在的情况下，会适当地取较大的常数，与普通权值进行区分。
无向图+不带权值图示
 无向图+带权值表示
 有向图+不带权值表示
 有向图+带权值表示

树

先序队（根左右)

先序队列也叫前序队列、先根队列、可记作根左右（二叉树父结点向下先左后右）

中序遍历（左根右）

后序遍历（左右根）

二叉树重建

|A\B|前序队列|中序队列|后序队列|
|:--:|:--:|:--:|
|前序队列|0|1|0|
|中序队列|1|0|1|
|后序队列|0|1|0|
故重构必有中序对列

动态规划 $(DP)$

是一种思想
不存在一种万能的思想

1.划分阶段

数列每一项： $i$

2.确定状态

状态： $f[i]$

3.确定决策并写出状态转移方程式

例如： $f[i]=f[i-1]+1$

【例题】最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$ ，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$ 。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$ 。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

提示

样例 1 解释

选取 $[3, 5]$ 子段 $\{3, -1, 2\}$ ，其和为 $4$ 。

数据规模与约定

对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$ 。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$ ， $-10^4 \leq a_i \leq 10^4$ 。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,ma;
int dp[N],a[N];
int main(){
	//结尾法
	//dp[i] 就表示 以下标 i 结尾的答案
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	
	//1 边界问题，开头？初始化？
	dp[1] = a[1]; 
	for(int i=2;i<=n;++i){
		if(dp[i-1]<0)	dp[i]=a[i];
		else	dp[i]=a[i]+dp[i-1];
	}
	//2 数据问题 
	ma=a[1]; 
	for(int i=1;i<=n;++i){
		ma=max(ma,dp[i]);
	} 
	cout<<ma;
	return 0;
}

最优化原理：（最优子结构）:

如果问题的 $\color{red}{\large\textbf{最优解所包含的子问题的解也是最优的}}$ ,就称该问题具有最优子结构，即满足该原理。

无后效性：

即某阶段状态 $\color{red}{\large\textbf{ 一旦确定}}$ ，就 $\color{red}{\large\textbf{ 不受这个状态以后的影响}}$ .也就是说，某状态以后的过程不会影响以前的状态， $\color{red}{\large\textbf{只与当前状态有关}}$ .

子问题重叠：

即 $\color{red}{\large\textbf{子问题之间是不独立的}}$ ,一个子问题在下一阶段决策中 $\color{red}{\large\textbf{可能被多次使用到}}$ .（该性质 $\color{red}{\large\textbf{并不是动态规划适用的必要条件}}$ ,但是如果没有这条性质，动态规划算法同其他算法相比就 $\color{red}{\large\textbf{不具备优势}}$ ）