【笔记】动态规划
前言
动态规划（Dynamic Programming）是c++算法学习当中十分重要而变化灵活的一部分分支，这种算法是通过递推的方式从而达到求出最优解的目的。
动态规划基本原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构：每个子问题的解是其本身的最优解。
无后效性：已经求解的子问题，不会再受到后续决策的影响。
动态规划中可能存在大量的子问题造成的答案重叠。
动态规划基本思路
将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的状态与特征。
寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式和关系。
按顺序求解每一个阶段的问题。
背包DP
0-1背包问题
[USACO07DEC]Charm Bracelet S - 洛谷
题目大意：
已知有 nnn 个物品，第 iii 个物品的重量 wiw_{i}wi，价值viv_{i}vi，背包的总容量 WWW。求背包可以容下的最大价值。
解题思路
该类型是典型的背包问题，可以设置一个二维数组 dpi,jdp_{i,j}dpi,j，表示在只能放下 ...
【笔记/模板】KMP算法
12345678910111213141516void solve(){ char s[N], p[N]; int lena, lenb; cin >> lena >> s + 1 >> lenb >> p + 1; for (int i = 1; i <= lenb; i++) { bool flag = true; for (int j = 1; j <= lena; j++) if (p[i + j - 1] != s[j]) { flag = false; break; } if (flag) cout << i - 1 << ' '; } }
朴素做法在极端条件下的时间复杂度为 O（n×m）O（n \times m）O（n×m）
【笔记/模板】Bellman-Ford 与 SPFA
Bellman-Ford求最短路和负环
时间复杂度：O(nm)O(nm)O(nm)
【模板/笔记】Johnson算法
12345678910111213141516171819202122bool Bellman_Ford(){ memset(dist, 0x3f, sizeof dist); for (int k = 1; k < n; k ++) for (int ver = 1; ver <= n; ver ++) for (int i = h[ver]; ~i; i = ne[i]) { int to = e[i]; if (dist[to] > dist[ver] + w[i]) dist[to] = dist[ver] + w[i]; } for (int ver = 1; ver <= n; ver ++) fo ...
【模板】素数筛
模板原题
1. 寻找因数筛法
时间复杂度：O(nn)O(n\sqrt n)O(nn)
核心模板代码如下：
1234567bool isprime(int n){ if (n < 2) return false; //0和1都不是 for(int i = 2; i * i <= n; ++ i) if(n % i == 0) return false; //有1和它本身以外的其他因子就不是素数了 return true;}
2. 埃氏筛法
时间复杂度：O(nloglogn)O(n\log \log n)O(nloglogn)
核心模板代码如下：
1234567891011121314void Eratosthenes(int n){ vis[0] = vis[1] = true; for (int i = 2; i <= n; i++) { if (!vis[i]) for (int j = 2 * i; j <= n; j += ...
