51工具盒子做题步骤 {#做题步骤}
- 先分析它的时间复杂度
- 出题人想要考什么算法
- 写代码
- 写测试数据
刷题网站 {#刷题网站}
https://www.dotcpp.com/oj/lanqiao/
https://www.lanqiao.cn/problems/
时间复杂度 {#时间复杂度}
https://www.acwing.com/blog/content/32/
时间限制为1s时:
- n ≤ 30 => O(2 ^n^ ), dfs+剪枝，状态压缩dp
- n ≤ 100 => O(n ^3^ )，floyd，dp，高斯消元
- n ≤ 1000 => O(n ^2^ )，O(n ^2^ logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
- n ≤ 10000 => O(n∗√n)，块状链表、分块、莫队
- n ≤ 100000 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
- n ≤ 1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
- n ≤ 10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
- n ≤ 10 ^9^ => O(√n)，判断质数
- n ≤ 10 ^18^ => O(logn)，最大公约数，快速幂，数位DP
- n ≤ 10 ^1000^ => O((logn) ^2^ )，高精度加减乘除
- n ≤ 10 ^100000^ => O(logk×loglogk)，k表示位数，高精度加减、FFT/NTT
快读快写 {#快读快写}
010203040506070809101112131415161718 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static StreamTokenizer cin = new StreamTokenizer(br);
public static int nextInt() throws Exception { cin.nextToken(); return (int) cin.nval; }
public static double nextDouble() throws Exception { cin.nextToken(); return cin.nval; } //只能读字母 public static String next() throws Exception { cin.nextToken(); return cin.sval; }
</code> </pre>基础算法 {#基础算法}
整数二分 {#整数二分}
https://oi-wiki.org/basic/binary/#二分答案
static boolean check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： static int bsearch_1(int l, int r) { while (l &lt; r) { int mid = (l + r) &gt;&gt;&gt; 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： static int bsearch_2(int l, int r) { while (l &lt; r) { int mid = (l + r + 1) &gt;&gt;&gt; 1; if (check(mid)) l = mid; else r = mid - 1; } return l; } </code> </pre> ### 一维前缀和 {#一维前缀和} [https://oi-wiki.org/basic/prefix-sum/#前缀和](https://oi-wiki.org/basic/prefix-sum/#%E5%89%8D%E7%BC%80%E5%92%8C) S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1] </code> </pre> ### 二维前缀和 {#二维前缀和} S[i, j] = 第i行j列格子左上部分所有元素的和 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1] </code> </pre> ### 一维差分 {#一维差分} 给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c </code> </pre> ### 二维差分 {#二维差分} 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c： S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c </code> </pre> 数据结构 {#数据结构} ------------ ### 单调栈 {#单调栈} <https://oi-wiki.org/ds/monotonous-stack/> 常见模型：找出每个数左边离它最近的比它大/小的数 ```````````````````````````````prism language-java int tt = 0; int[] stk = new int[n + 1]; for (int i = 1; i <= n; i++) { while (tt > 0 && check(stk[tt], i)) { tt--; } stk[++tt] = i; } </code> </pre> ### 单调队列 {#单调队列} <https://oi-wiki.org/ds/monotonous-queue/> 常见模型：找出滑动窗口中的最大值/最小值 ``````````````````````````````prism language-java int hh = 0, tt = -1; int[] q = new int[n]; for (int i = 0; i < n; i++) { while (hh <= tt && check_out(q[hh])) { hh++; } while (hh <= tt && check(q[tt], i)) { tt--; } q[++tt] = i; } </code> </pre> ### KMP {#kmp} <https://oi-wiki.org/string/kmp/> 求模式串的Next数组： `````````````````````````````prism language-java int[] ne = new int[m + 1]; ne[1] = 0; for (int i = 2, j = 0; i <= m; i++) { while (j != 0 && p[i] != p[j + 1]) { j = ne[j]; } if (p[i] == p[j + 1]) { j++; } ne[i] = j; } </code> </pre> 匹配： ````````````````````````````prism language-java for (int i = 1, j = 0; i <= n; i++) { while (j != 0 && s[i] != p[j + 1]) { j = ne[j]; } if (s[i] == p[j + 1]) { j++; } if (j == m) { j = ne[j]; // 匹配成功后的逻辑 } } </code> </pre> ### 并查集 {#并查集} <https://oi-wiki.org/ds/dsu/> ```````````````````````````prism language-java static int n; static int[] p = new int[n + 1]; // 存储每个点的祖宗节点 // 返回x的祖宗节点 static int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } // 初始化，假定节点编号是1~n static void init() { for (int i = 1; i &lt;= n; i++) { p[i] = i; } } // 合并a和b所在的两个集合 static void union(int a, int b) { p[find(a)] = find(b); } </code> </pre> ### 线段树 {#线段树} <https://oi-wiki.org/ds/seg/> ``````````````````````````prism language-java static int[] a; static int[] d; // 通过子节点计算父节点 static int pushUp(int l, int r) { // 计算父节点的值 // ... } static void build(int s, int t, int p) { // 对 [s,t] 区间建立线段树,当前根的编号为 p if (s == t) { d[p] = a[s]; return; } int m = s + ((t - s) &gt;&gt; 1); // 移位运算符的优先级小于加减法，所以加上括号 // 如果写成 (s + t) &gt;&gt; 1 可能会超出 int 范围 build(s, m, p * 2); build(m + 1, t, p * 2 + 1); // 递归对左右区间建树 d[p] = pushUp(d[p * 2], d[(p * 2) + 1]); } static int getRes(int l, int r, int s, int t, int p) { // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号 if (l &lt;= s &amp;&amp; t &lt;= r) { return d[p]; // 当前区间为询问区间的子集时直接返回当前区间的和 } int m = s + ((t - s) &gt;&gt; 1), sum = 0; int lv = 0, rv = 0; // 默认值 if (l &lt;= m) { lv = getRes(l, r, s, m, p * 2); } // 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子 if (r &gt; m) { rv = getRes(l, r, m + 1, t, p * 2 + 1); } return pushUp(lv, rv); } </code> </pre> 图论 {#图论} -------- ### 邻接矩阵 {#邻接矩阵} [https://oi-wiki.org/graph/save/#邻接矩阵](https://oi-wiki.org/graph/save/#%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5) `````````````````````````prism language-java static int n; static int[][] g = new int[n + 1][n + 1]; // 存储边a->b // 添加一条边a-&gt;b static void add(int a, int b) { g[a][b] = 1; } </code> </pre> ### 邻接表 {#邻接表} [https://oi-wiki.org/graph/save/#邻接矩阵](https://oi-wiki.org/graph/save/#%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5) ````````````````````````prism language-java //n个点，m条单向边 static int[] h = new int[n + 1]; // 存储每个点的单链表的头结点 static int[] e = new int[m + 1]; // 存储每个点的可达点 static int[] ne = new int[m + 1]; // 存储每个点的下一个可达点 static int idx; // 添加一条边a-&gt;b static void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } // 初始化 static void init() { Arrays.fill(h, -1); } </code> </pre> ### 深度优先遍历 {#深度优先遍历} <https://oi-wiki.org/graph/dfs/> ```````````````````````prism language-java static int n,m; static boolean[] st = new boolean[n + 1]; // 表示点是否被遍历过 static int[] h = new int[n + 1], e = new int[m + 1], ne = new int[m + 1]; static void dfs(int u) { st[u] = true; // 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { dfs(j); } } } </code> </pre> ### 宽度优先遍历 {#宽度优先遍历} <https://oi-wiki.org/graph/bfs/> ``````````````````````prism language-java Queue<Integer> q = new LinkedList<>(); boolean[] st = new boolean[n + 1]; // 表示点是否被遍历过 st\[1\] = true; // 表示1号点已经被遍历过 q.offer(1); while (!q.isEmpty()) { int t = q.poll(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; // 表示点j已经被遍历过 q.offer(j); } } } </code> </pre> ### 拓扑排序 {#拓扑排序} <https://oi-wiki.org/graph/topo/> `````````````````````prism language-java //n 表示点数 Queue<Integer> q = new LinkedList<>(); // 存储拓扑序列 int[] d = new int[n + 1]; // 存储点的入度 // 统计每个点的入度 for (int i = 1; i \<= n; i++) { for (int j = h\[i\]; j != -1; j = ne\[j\]) { int k = e\[j\]; d\[k\]++; } } // 将入度为0的点入队 for (int i = 1; i \<= n; i++) { if (d\[i\] == 0) { q.offer(i); } } while (!q.isEmpty()) { int t = q.poll(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (--d[j] == 0) { q.offer(j); } } } // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。 boolean hasTopologicalOrder = (tt == n - 1); </code> </pre> ### 朴素Dijkstra算法 {#朴素dijkstra算法} 时间复杂度：O(n\^2 + m), 其中 n 表示点数，m 表示边数 [https://oi-wiki.org/graph/shortest-path/#dijkstra-算法](https://oi-wiki.org/graph/shortest-path/#dijkstra-%E7%AE%97%E6%B3%95) ````````````````````prism language-java static int n; static int[][] g = new int[n + 1][n + 1]; // 存储每条边 static int[] dist = new int[n + 1]; // 存储1号点到每个点的最短距离 static boolean[] st = new boolean[n + 1]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 static int dijkstra() { Arrays.fill(dist, 0x3f3f3f3f); dist[1] = 0; for (int i = 0; i &lt; n - 1; i++) { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j &lt;= n; j++) { if (!st[j] &amp;&amp; (t == -1 || dist[t] &gt; dist[j])) { t = j; } } // 用t更新其他点的距离 for (int j = 1; j &lt;= n; j++) { dist[j] = Math.min(dist[j], dist[t] + g[t][j]); } st[t] = true; } if (dist[n] == 0x3f3f3f3f) { return -1; } return dist[n]; } </code> </pre> ### SPFA算法（队列优化的Bellman-Ford算法） {#spfa算法（队列优化的bellman-ford算法）} 时间复杂度：平均情况下 O(m), 最坏情况下 O(nm), 其中 n 表示点数，m 表示边数 [https://oi-wiki.org/graph/shortest-path/#队列优化spfa](https://oi-wiki.org/graph/shortest-path/#%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96spfa) ```````````````````prism language-java static int n, m; // 总点数, 总边数 static int[] h = new int[n + 1]; static int[] w = new int[m + 1]; static int[] e = new int[m + 1]; static int[] ne = new int[m + 1]; static int[] dist = new int[n + 1]; // 存储每个点到1号点的最短距离 static boolean[] st = new boolean[n + 1]; // 存储每个点是否在队列中 // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 static int spfa() { Arrays.fill(dist, Integer.MAX_VALUE); dist[1] = 0; Queue&lt;Integer&gt; q = new LinkedList&lt;&gt;(); q.offer(1); st[1] = true; while (!q.isEmpty()) { int t = q.poll(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] &gt; dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { // 如果队列中已存在j，则不需要将j重复插入 q.offer(j); st[j] = true; } } } } if (dist[n] == Integer.MAX_VALUE) { return -1; } return dist[n]; } </code> </pre> ### SPFA判断图中是否存在负环 {#spfa判断图中是否存在负环} 时间复杂度：O(nm), 其中 n 表示点数，m 表示边数 ``````````````````prism language-java static int n, m; // 总点数, 总边数 static int[] h = new int[n + 1]; static int[] w = new int[m + 1]; static int[] e = new int[m + 1]; static int[] ne = new int[m + 1]; static int[] dist = new int[n + 1]; // dist[x]存储1号点到x的最短距离 static int[] cnt = new int[n + 1]; // cnt[x]存储1到x的最短路中经过的点数 static boolean[] st = new boolean[n + 1]; // 存储每个点是否在队列中 // 如果存在负环，则返回true，否则返回false。 static boolean spfa() { Queue&lt;Integer&gt; q = new LinkedList&lt;&gt;(); for (int i = 1; i &lt;= n; i++) { q.offer(i); st[i] = true; } while (!q.isEmpty()) { int t = q.poll(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] &gt; dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] &gt;= n) { // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环 return true; } if (!st[j]) { q.offer(j); st[j] = true; } } } } return false; } </code> </pre> ### Floyd算法 {#floyd算法} 时间复杂度：O(n\^3), 其中 n 表示点数 [https://oi-wiki.org/graph/shortest-path/#floyd-算法](https://oi-wiki.org/graph/shortest-path/#floyd-%E7%AE%97%E6%B3%95) `````````````````prism language-java static final int INF = 0x3f3f3f3f; static int n; // 总点数 static int[][] d = new int[n + 1][n + 1]; // 存储最短距离 // 初始化 static void init() { for (int i = 1; i &lt;= n; i++) { for (int j = 1; j &lt;= n; j++) { if (i == j) { d[i][j] = 0; } else { d[i][j] = INF; } } } } // 算法结束后，d[a][b]表示a到b的最短距离 static void floyd() { for (int k = 1; k &lt;= n; k++) { for (int i = 1; i &lt;= n; i++) { for (int j = 1; j &lt;= n; j++) { d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); } } } } </code> </pre> ### 朴素版Prim算法 {#朴素版prim算法} 时间复杂度：O(n\^2 + m), 其中 n 表示点数，m 表示边数 [https://oi-wiki.org/graph/mst/#prim-算法](https://oi-wiki.org/graph/mst/#prim-%E7%AE%97%E6%B3%95) ````````````````prism language-java static final int INF = 0x3f3f3f3f; static int n; // n表示点数 static int[][] g = new int[n + 1][n + 1]; // 邻接矩阵，存储所有边 static int[] dist = new int[n + 1]; // // 存储其他点到当前最小生成树的距离 static boolean[] st = new boolean[n + 1]; // 存储每个点是否已经在生成树中 // 如果图不连通，则返回INF(值是0x3f3f3f3f)，否则返回最小生成树的树边权重之和 static int prim() { Arrays.fill(dist, INF); int res = 0; for (int i = 0; i &lt; n; i++) { int t = -1; for (int j = 1; j &lt;= n; j++) { if (!st[j] &amp;&amp; (t == -1 || dist[t] &gt; dist[j])) { t = j; } } if (i != 0 &amp;&amp; dist[t] == INF) { return INF; } if (i != 0) { res += dist[t]; } st[t] = true; for (int j = 1; j &lt;= n; j++) { dist[j] = Math.min(dist[j], g[t][j]); } } return res; } </code> </pre> ### Kruskal 算法 {#kruskal-算法} 时间复杂度：O(m \* log(m)), 其中 n 表示点数，m 表示边数 [https://oi-wiki.org/graph/mst/#kruskal-算法](https://oi-wiki.org/graph/mst/#kruskal-%E7%AE%97%E6%B3%95) ```````````````prism language-java static int n, m; // n是点数，m是边数 static int[] p = new int[n + 1]; static int[][] e = new int[m + 1][3]; public static int find(int x) { // 并查集核心操作 if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } public static int kruskal() { Arrays.sort(e, 0, m, (o1, o2) -> o1[2] - o2[2]); for (int i = 1; i &lt;= n; i++) { p[i] = i; // 初始化并查集 } int res = 0, cnt = 0; for (int i = 0; i &lt; m; i++) { int a = e[i][0], b = e[i][1], w = e[i][2]; a = find(a); b = find(b); if (a != b) { // 如果两个连通块不连通，则将这两个连通块合并 p[a] = b; res += w; cnt++; } } //没有最小生成树 if (cnt &lt; n - 1) { return Integer.MAX_VALUE; } return res; } </code> </pre> 数学知识 {#数学知识} ------------ ### 试除法判定质数 {#试除法判定质数} ``````````````prism language-java static boolean isPrime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i++) { if (x % i == 0) { return false; } } return true; } </code> </pre> ### 试除法分解质因数 {#试除法分解质因数} `````````````prism language-java static void divide(int x) { for (int i = 2; i <= x / i; i++) { if (x % i == 0) { int s = 0; while (x % i == 0) { x /= i; s++; } System.out.println(i + " " + s); } } if (x > 1) { System.out.println(x + " " + 1); } System.out.println(); } </code> </pre> ### 线性筛法求素数 {#线性筛法求素数} [https://oi-wiki.org/math/number-theory/sieve/#素数筛法](https://oi-wiki.org/math/number-theory/sieve/#%E7%B4%A0%E6%95%B0%E7%AD%9B%E6%B3%95) ````````````prism language-java static int n;//求小于等于n的素数 static int[] primes = new int[n + 1]; // 存储所有素数 static boolean[] st = new boolean[n + 1]; // 存储x是否被筛掉 static int cnt = 0; static void getPrimes(int n) { for (int i = 2; i &lt;= n; i++) { if (!st[i]) { primes[cnt++] = i; } for (int j = 0; j &lt; cnt &amp;&amp; primes[j] &lt;= n / i; j++) { st[primes[j] * i] = true; if (i % primes[j] == 0) { break; } } } } </code> </pre> ### 试除法求所有约数 {#试除法求所有约数} ```````````prism language-java static List<Integer> getDivisors(int x) { List<Integer> res = new ArrayList<>(); for (int i = 1; i <= x / i; i++) { if (x % i == 0) { res.add(i); if (i != x / i) { res.add(x / i); } } } Collections.sort(res); return res; } </code> </pre> ### 约数个数和约数之和 {#约数个数和约数之和} 如果 N = p1\^c1 \* p2\^c2 \* ... \* pk\^ck \* 约数个数： (c1 + 1) \* (c2 + 1) \* ... \* (ck + 1) \* 约数之和： (p1\^0 + p1\^1 + ... + p1\^c1) \* ... \* (pk\^0 + pk\^1 + ... + pk\^ck) ### 欧几里得算法 {#欧几里得算法} 求最大公因数 [https://oi-wiki.org/math/number-theory/gcd/#欧几里得算法](https://oi-wiki.org/math/number-theory/gcd/#%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95) ``````````prism language-java static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } </code> </pre> ### 求欧拉函数 {#求欧拉函数} 欧拉函数，即 \varphi(n) ，表示的是小于等于 n 和 n 互质的数的个数。 <https://oi-wiki.org/math/number-theory/euler/> `````````prism language-java static int phi(int x) { int res = x; for (int i = 2; i <= x / i; i++) { if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) { x /= i; } } } if (x > 1) { res = res / x * (x - 1); } return res; } </code> </pre> ### 筛法求欧拉函数 {#筛法求欧拉函数} [https://oi-wiki.org/math/number-theory/sieve/#筛法求欧拉函数](https://oi-wiki.org/math/number-theory/sieve/#%E7%AD%9B%E6%B3%95%E6%B1%82%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0) ````````prism language-java static int n; static int[] primes = new int[n + 1]; // 存储所有素数 static int[] euler = new int[n + 1]; // 存储每个数的欧拉函数 static boolean[] st = new boolean[n + 1]; // 存储x是否被筛掉 static int cnt; // 存储素数的个数 static void getEulers(int n) { euler[1] = 1; for (int i = 2; i <= n; i++) { if (!st[i]) { primes[cnt++] = i; euler[i] = i - 1; } for (int j = 0; j < cnt && primes[j] <= n / i; j++) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } } } </code> </pre> ### 快速幂 {#快速幂} 求 m\^k mod p，时间复杂度 O(log(k))。 qmi(m, p - 2, p) 等于m模p下的乘法逆元 <https://oi-wiki.org/math/binary-exponentiation/> ```````prism language-java static int qmi(int m, int k, int p) { int res = 1 % p; int t = m; while (k != 0) { if ((k & 1) == 1) { res = res * t % p; } t = t * t % p; k >>>= 1; } return res; } </code> </pre> ### 扩展欧几里得算法 {#扩展欧几里得算法} 求x, y，使得ax + by = gcd(a, b) 若exgcd(a, b, x, y) == 1 则 (x\[0\]%b+b)%b 是a模b下的乘法逆元 [https://oi-wiki.org/math/number-theory/gcd/#扩展欧几里得算法](https://oi-wiki.org/math/number-theory/gcd/#%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95) ``````prism language-java static int exgcd(int a, int b, int[] x, int[] y) { if (b == 0) { x[0] = 1; y[0] = 0; return a; } int d = exgcd(b, a % b, y, x); y[0] -= (a/b) * x[0]; return d; } </code> </pre> ### 线性求乘法逆元 {#线性求乘法逆元} <https://oi-wiki.org/math/number-theory/inverse/> `````prism language-java static int n, p; static long[] inv = new long[n + 1]; static void get() { inv[1] = 1; for (int i = 2; i &lt;= n; ++i) { inv[i] = (long)(p - p / i) * inv[p % i] % p; }g } </code> </pre> 贪心 {#贪心} -------- <https://oi-wiki.org/basic/greedy/> 每一步行动总是按某种指标选取最优的操作。 动态规划 {#动态规划} ------------ ### 分析法 {#分析法} ````prism language-mermaid graph LR A\[定义问题\] --\> B\[确定子问题\] B --\> C\[确定状态\] C --\> D\[确定状态转移方程\] D --\> E\[确定初始条件和边界条件\] E --\> F\[计算最优解\] F --\> G\[返回最优解\] </code> </pre> ### 闫氏dp分析法 {#闫氏dp分析法} <https://www.acwing.com/file_system/file/content/whole/index/content/1084122/> ```prism language-mermaid graph LR A\[问题\] --\> B\[状态表示\] B --\> C\[集合\] B --\> D\[属性\] A --\> E\[状态计算\] </code> </pre> 内容参考 {#内容参考} ------------ <https://oi-wiki.org> <https://www.acwing.com/activity/content/introduction/11/> ``` ```` ````` `````` ``````` ```````` ````````` `````````` ``````````` ```````````` ````````````` `````````````` ``````````````` ```````````````` ````````````````` `````````````````` ``````````````````` ```````````````````` ````````````````````` `````````````````````` ``````````````````````` ```````````````````````` ````````````````````````` `````````````````````````` ``````````````````````````` ```````````````````````````` ````````````````````````````` `````````````````````````````` ```````````````````````````````
![[ChatGPT解决方案]生成 nginx 自签名证书](https://img1.51tbox.com/static/2024-09-03/uCaeHqLsmksW.png)
