图论相关
题目来源
题意
给定一张 \(n\) 个点 \(m\) 条边的无向带权图，找到图中一个权值最小的 \(\text{Q}\) 。
\(\text{Q}\) 定义为一个环带上一条与这个环相连且不在环上的边。
\(4\le n \le 300 , 4\le m \le \frac{n(n-1)}{2}\) 。
思路
考虑枚举每一条边作为 \(\text{Q}\) 的尾巴，然后把这条边删去，从这条边的一个端点跑一个单源最短路。然后再枚举两个点，能够轻松找到不经过这条边的一个最小环。
这样枚举尾巴的时间复杂度为 \(O(n^2)\) ，找最小环的时间复杂度为 \(O(n^2)\) ，总时间复杂度为 \(O(n^4)\) ，这是难以接受的。
考虑到一个环会占用一个点相连的两条边，最劣情况下尾巴也是第三小的边，所以我们第一步不需要枚举所有的边作为尾巴，只需要枚举每个点相连的前三小的边做尾巴即可。这样枚举尾巴的时间复杂度降为 \(O(n)\) ，总时间复杂度降为 \(O(n^3)\) 。
动态规划
题目来源
题意
给定一个长度为 \(n\) 的数列 \(a\) ，把 \(a\) 分成任意组，每组的不和谐度定义为该组内元组的最大值与最小值之差，求所有不和谐度之和不超过 \(m\) 的分组方案数，对 \(10^9 + 7\) 取模。
\(1 \le n \le 200 , 0 \le m \le 10^3 , 1 \le a_i \le 500\) 。
思路
由于不和谐度是最大值与最小值的差，乱找不好找，考虑对数列 \(a\) 从小到大进行排序，然后依次考虑每个数的分组情况。
考虑设 \(f_{i,j,k}\) 为选了前 \(i\) 个位置，有 \(j\) 个没有结束的组，当前选的总不和谐度为 \(k\) 的方案数。
考虑若有一个组选了 \(a_{p_1} , a_{p_2} , \cdots, a_{p_n}\) 这些元素，且 \(p_1 < p_2 < \cdots < p_n\) ，则不和谐度为 \(a_{p_n} - a_{p_1}\) 。
考虑到 \(a_{p_n} - a_{p_1} = (a_{p_n} - a_{p_{n-1}}) + (a_{p_{n-1}} - a_{p_{n-2}}) + \cdots + (a_{p_2} - a_{p_1})\) ，所以每次向之前的某一组中加入 \(a_{i + 1}\) 这个元素时，所有的组都会被增加 \(a_{i + 1} - a_{i}\) 的不和谐度，利用这个可以找到转移时 \(k\) 的增量。
再考虑转移的几种情况：
当前点单独成组：\(f_{i + 1 , j , k + j \times (a_{i + 1} - a_i)} \leftarrow f_{i,j,k}\) 。
当前点加入一个组中，即不作为最大值，也不作为最小值：\(f_{i + 1, j, k + j \times (a_{i+1} - a_{i})} \leftarrow f_{i, j, k}\) 。
当前点新开一个组，且作为最小值：\(f_{i + 1, j + 1 , k + j \times(a_{i + 1} - a_{i})} \leftarrow f_{i,j,k}\) 。
当前点结束一个组，且作为最大值：\(f_{i + 1, j - 1, k + j \times (a_{i+1}-a_{i})} \leftarrow f_{i,j,k}\) 。
复杂度可以做到 \(O(n^2 m)\) 。
题目来源
题意
有 \(n\) 个物品和四个盒子 \(A,B,C,D\) ，每个物品都有一个重量 \(w_i\) ，你需要将每个物品放入一个盒子中。
给定 \(k_1,k_2,k_3,k_4\) ，设 \(|X|\) 表示 \(X\) 盒子内物品的总重，一个合法的装盒方案最终应当满足如下的条件：
\[ |A|+|B|\le k_1 \]
\[ |C|+|D|\le k_2 \]
\[ |A|+|C|\le k_3 \]
\[ |B|+|D|\le k_4 \]
求有多少种合法的装盒方案，答案对 \(998244353\) 取模。
\(1\le n \le 100 , 1 \le k_i \le 1000\) 。
思路
脑筋慢转弯题（bushi
最直接的思路就是一个四维的背包 \(\text{dp}\) ，设 \(f_{i,a,b,c,d}\) 表示前 \(i\) 件物品，\(A\) 和 \(B\) 总共放了 \(a\) ，\(C\) 和 \(D\) 总共放了 \(b\) ，\(A\) 和 \(C\) 总共放了 \(c\) ， \(B\) 和 \(D\) 总共放了 \(d\) ，满足以上限制的总方案数。转移就考虑当前物品放入哪一个箱子。
发现四个盒子两两组合总共有 \(6\) 种，但题目中只限制了 \(4\) 种，于是找一下关系，不难发现前两个式子加起来是 \(|A| + |B| + |C| + |D|\) ，后两个式子加起来也是 \(|A| + |B| + |C| + |D|\) 。
设 \(w_i\) 的前缀和是 \(sum_i\) ，那么到第 \(i\) 个位置，由于每个物品一定会被放入四个盒子其中之一，所以 \(a + c = |A| + |B| + |C| + |D| = sum_i\) ，\(b + d = |A| + |B| + |C| + |D| = sum_i\) ，所以我们找到了 \(a,c\) 之间和 \(b,d\) 之间的关系，这样可以压掉两维，时间复杂度变成了 \(O(n k ^2)\) 。