题意有一个 $m(m\le 20)$ 个点 $e$ 条边的无向图，有 $n(n\le 100)$ 个时刻需要从 $1\rightarrow m$ （保证可以到达）。每个点都有些时刻无法通行，如果更换道路还需要额外交 $k$ 元。求最小花费。题解用 $f[i]$ 表示前 $i$ 个时刻的最小花费，$x$ 表示最短路径。枚举与 $i$ 路径相同的区间起点 $j$ ，可以得到方程：$$f[i]=\...
题意给出一个数字串，要求用逗号将其分成若干个严格递增的数。如果有多解要求最后一个数最小，如果还有多解要求字典序最大。数字串长度 $\le 500$ 。题解先正着推出最后一个最小的数。用 $f[i]$ 代表以 $i$ 结尾的数的最近的开头，可以逆序枚举 $j$ ，如果 $[f[j-1],j-1] < [j,i]$ ，那么 $f[i]=j$ 。然后反着推一个最大的数。用 $g[i]$ 表示...
题意有一个只有 $-1,0,1$ 的序列，每次操作可以使 s[i]+=s[i-1] ，求最少要操作几次使得序列单调不降。无解输出 BARK序列长度 $N\le 1000000$ 。题解用 $f[i][j]$ 表示前 $i$ 个数，$s[i]=j-1$ 时的最少操作次数。然后对于每一位的值分类讨论即可。代码里很显然了，我懒得再写一遍了。#include<bits/stdc++.h>...
题意有一个序列，要求修改尽可能少的数，使得这个序列变成单调上升序列。输出最少需要修改多少个数，以及在修改最少的前提下，每个数改变的绝对值之和的最小值。序列长度 $N\le 35000$ 。题解子问题1如果只是单调不降就很简单，但这题要求单调上升。假设可以保留 $S_i,S_j \ (i < j)$ ，则需要满足 $S_j - S_i \geq j-i$ ，即 $S_j - j\geq ...
题意有 $A,B$ 两个字符串，要从 $A$ 中选出 $k$ 个子串，按原顺序排列后形成 $B$ 。求方案数。$A,B$ 的长度为 $N,M$ ，$N\le 1000 \ , \ M\le 200$ 。题解用 $f[i][j][k]$ 表示取到 $A_i,B_j$ ，选了 $k$ 个子串的方案数。可以枚举当前子串的长度 $l$ ，这样要求 $A_{[i-l+1,i]}$ 和 $B_{[j-l...
双倍经验：洛谷1868 饥饿的奶牛题意从 $N$ 个区间中选取一些不重叠的区间，使得总长度最大。$N\le 10000 \ \ L,R\le 30000$ 。题解用 $f[i]$ 表示前 $i$ 个数选取区间的最大总长度，答案即为 $f[n]$ 。如果存在一个区间 $[y,x]$ ，那么 $f[x]$ 就可以从 $f[y]$ 转移过来。方程式为：$$f[x] = \max \begin{ca...
题意有 $N$ 个格子，每个格子有权值。最开始每次只能跳 $d$ 格，可以通过改进跳 $d-g..d+g$ 格。求满足能获得最少 $k$ 权值的最小的 $g$ 。$N\le 500000$ 。题解可以对 $g$ 二分答案，然后进行验证。令 $f[i]$ 为前 $i$ 个格子可以获得的最大权值，转移方程式为：$$f[i] = \max_{j=1}^{i-1} f[j]+s[i] \ (d-g\...
双倍经验：洛谷2034 选择数字题意从一个数列中选出一些数，要求不能有超过 $k$ 个连续的数，求这些数的最大和。数列长度 $N\le 100000$ 。题解令 $f[i]$ 表示前 $i$ 个数的最优解，$sum[i]$ 表示前缀和，转移方程式为：$$f[i] = \max_{j=i-k}^i f[j-1] + sum[i] - sum[j]$$$$f[i] = \max_{j=i-k}^...
双倍经验：洛谷2687 逢低吸纳，全部改成 double 就可以水过。题意求最长下降子序列的长度和个数。如果两个序列的值相同，则认为这两个序列相同，只算一个。序列长度 $N\le 5000$ 。题解长度很好求，用 $f[i]$ 表示以 $i$ 结尾的最长下降子序列的长度：$$f[i] = \max_{j=1}^{i-1} f[j]+1 \ (s[j] > s[i]) \tag{1}$...
题意用两个栈进行排序，只有入栈和出栈操作，求字典序最小的操作序列。如果无法排序输出 No 。数列长度 $N\le 1000$ 。题解先考虑单栈排序。如果存在 $i < j < k$ 但 $S_k < S_i < S_j$ 就无法进行排序。这道题有两个栈，可以对所有矛盾关系 $(i,j)$ 建边，然后跑一遍 $\text{dfs}$ 进行染色，判断是否有矛盾。枚举所有的...