动态规划是一种常用的方法，通过记录“状态”将原问题划分为多个子问题从而使原问题得到解决。
树上 DP
树，很显然，每颗子树都是一颗完整的树，很符合动态规划的适用范围，也是一种很常考的数据结构。 树上的DP大多数情况下都采用自下而上的递推方法， 在树上的 DP 大致分一下几种：
- 基本的树形 DP
- 树上背包
- 换根 DP
接下来将在本文中一一介绍。
基本树形 DP
一般的树形dp 一般看子树的状态决策子树根结点就可以了。
例题: P1122
这道例题比较特殊，往下dfs的看子树值有没有大于0，显然可以看出大于0的子树一定对答案有贡献。
#include<bits/stdc++.h>
using namespace std;
const int N = 16000 + 5;
vector<long long> G[N];
long long n,f[N],d[N];
void dfs(long long r, int prev){
for(int i = 0; i < G[r].size(); i++){
if(G[r][i] == prev) continue;
dfs(G[r][i], r);
d[r] += max(d[G[r][i]],0ll);
}
}
int main(){
scanf("%lld",&n);
memset(f,-1,sizeof(f));
for(int i = 1; i <= n; i++)
scanf("%lld",&d[i]);
for(int i= 1; i < n; i++)
{
long long x,y;
scanf("%lld%lld",&y,&x);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0);
long long ans=-2147483647;
for(int i=1;i<=n;i++)
ans=max(ans,d[i]);
printf("%lld\n",ans);
return 0;
}树上背包
在树上做的背包问题
例题: P2014
这题可以将科目建成一棵树，在树上作 DP 。为什么呢？显而易见，每颗子树的决策在子树所分配的选课数量固定的前提下所能有的最大值是固定的， 故可以枚举每颗子树分配的选课数量，那么边界条件就是对于每个节点，不选就是0，选一科就是自己的值（最起码要选自己，不然之后的都选不了）。 这样自底向上就可以进行递推了。
可以利用背包的思路，令f[i][j]为在第i个节点分配j个课可以得到的最大值，将课看作背包重量，就可以进行 DP 了。
这里又有一个小优化：可以知道每个节点能选的科目至多为max(m, sz[i])。所以可以在dfs的时候同时处理出节点的size，可以O(nm^2) -> O(nm)
下面是实现：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 5;
int f[maxn][maxn];
int a[maxn];
int sz[maxn];
vector<int> G[maxn];
int n, m;
void dfs(int u, int p){
f[u][0] = 0;
f[u][1] = a[u];
sz[u] = 1;
for(auto i : G[u]){
if(i == p) continue;
dfs(i, u);
sz[u] += sz[i];
for(int j = min(m, sz[u]);j > 0;j --){
for(int x = 1;x < j && x <= sz[u];++x){
f[u][j] = max(f[u][j], f[u][j-x] + f[i][x]);
}
}
}
}
int main(){
cin>>n>>m;
m += 1;
for(int i = 1;i <= n;++i){
int s, k;
cin>>k>>s;
G[k].push_back(i);
a[i] = s;
}
memset(f, 0xc0, sizeof f); //0xc0 对应 0x3f 取负
dfs(0, 0);
cout<<f[0][m]<<endl;
return 0;
}换根 DP
较为特殊的一类树上 DP 。 适用于结果没有固定根结点，需要找到合适的根结点的问题。
换根 DP 的关键在于找到树上节点与节点之间值的关系，只要满足这个关系，就可以进行换根 DP。 首先任意选择一个点进行dfs，然后通过 DP 得出与它相邻的点的值，以此类推，求出答案
例题: P3478
显然有 f[u] = 1 + f[v], 可以对每个可到达点v进行递归的操作。一次dfs在O(n)的时间复杂度内可以完成
然后进行 换根 。
换根，顾名思义，将当前的根更换。由于之前我们是用u作为根结点，所以得出f[u]应该是正确的答案。那么，我们就可以看看能不能利用这个正确值去得到f[v]的正确值。
如图，可以推出状态转移方程。则第二次dfs的时候根据方程转移即可求出所有点的答案，取最大值就可以了。
代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 5;
int n;
long long sz[maxn];
long long f[maxn];
vector<int> G[maxn];
void dfs(int u, int p){
f[u] = 0;
sz[u] = 1;
for(auto i : G[u]){
if(i == p) continue;
dfs(i, u);
f[u] += f[i] + sz[i];
sz[u] += sz[i];
}
}
void chg(int u, int p){
for(auto i : G[u]){
if(i == p) continue;
f[i] += f[u] - (f[i] + sz[i]) + (n - sz[i]);
chg(i, u);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i = 1;i < n;++i){
int u, v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
chg(1, 0);
long long ans = -1;
int cur = 0;
for(int i = 1;i <= n;++i){
if(ans < f[i]){
cur = i;
ans = f[i];
}
}
cout<<cur<<endl;
return 0;
}状压 DP
状态压缩 DP，适合处理哪些能够将状态压缩进一个比较小的范围以便用数组存储的问题。状态压缩的基本思路是找到状态和状态之间的关联从而解决问题。其中又分为子集转移和轮廓信息两个小点。
前置：二进制常用操作
最常用的压缩方式是将状态以二进制的方式压缩并存储起来，所以二进制的操作在状压 DP 中非常重要。下面介绍一些常见的二进制处理方法。
| 内容 | 实现 |
|---|---|
| 取全集 |
ALL=(1<<n)-1 或 ALL=(1<<n+1)-1
|
| 求和 | for(int i=1;i<=ALL;++i) sum[i]=sum[i^lowbit(i)]+sum[lowbit(i)] |
| 枚举ALL的子集 | for(int j = ALL;j != 0;j = (j-1)&ALL) |
| 加入第i位（设为1） | A = A \| (1 << i) |
| 删除第i位（设为0） |
A = A & ~(1 << i) or A = A ^ (1 << i)
|
| 判断第i位 | if (A & (1 << i)) |
| 求补集 | A = A ^ ((1 << n) - 1) |
| 求并集 | A \| B |
| 求交集 | A & B |
朴素状压 DP
传统的状态压缩，二进制，考虑一下如何合并即可
例题: P1433
将每两个点之间的距离处理出来存好，注意枚举时先选择好起始状态，最后再枚举末状态。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 15+1;
const double inf = 1e100;
struct Node{
double x, y;
};
int n;
double f[1<<maxn][maxn];
double w[maxn][maxn];
Node a[maxn];
int main(){
cin>>n;
int ALL = (1<<n+1)-1;
f[1][0] = 0;
a[0].x = 0;
a[0].y = 0;
for(int i = 1;i <= n;++i){
cin>>a[i].x>>a[i].y;
}
for(int i = 0;i <= n;++i){
for(int j = 0;j <= n;++j){
w[i][j] = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
}
}
for(int i = 2;i <= ALL;++i){
for(int j = 0;j <= n;++j){
if((i>>j)&1){
f[i][j] = inf;
for(int k = 0;k <= n;++k){
if(k != j && ((i >> k) & 1)){
f[i][j] = min(f[i^(1<<j)][k] + w[k][j], f[i][j]);
}
}
}
}
}
double ret = inf;
for(int i = 0;i <= n;++i) ret = min(ret, f[ALL][i]);
cout<<fixed<<setprecision(2)<<ret<<endl;
return 0;
}子集转移
子集转移通过在子集之间建立转移方程式达到优化的效果。
用上面的枚举子集的方式可以降低复杂度。
数位 DP
一般使用记忆化搜索。
一般来说，数位 DP 需要记忆很多状态，包括但不限于现在填了几个数位，有没有前导0，是不是“特殊状态”等。
所谓特殊状态，即数位值域是否达到末尾。i.e.: 对于0-1145，分为完整的 0-999 和不完整的 1000-1145。
算法的内容比较固定，基本模版如下：
const int maxn = 100;
int f[maxn][2][2];
int dgt[maxn]; // set to -1 by default
int dfs(int pos, int o, int z) {
int res = 0;
if (pos == 0) return 1;
if (~f[pos][o][z]) return f[pos][o][z];
int maxDgt = (o ? dgt[pos]:9);
for (int i = 0;i < maxDgt;++i) {
// if ( condition ) continue -> exclude illegal situations
res += dfs(pos-1, o && i == maxDgt, z && i == 0);
}
return res;
}
int work(int x){
int len = 0;
while(x){
dgt[++len] = x % 10;
x /= 10;
}
return dfs(len, 1, 1);
}DP 优化
矩阵快速幂优化
其实就是用矩阵来递推啦
先构造一个转移矩阵，再构造一个初始矩阵，对于转移只有一维并且 dp 都只有“一次”(即转移中不存在 f[i] * f[j] )的 转移，可以采取这种方法。
例题: P1707
题目中给出了明确的转移，显然每个转移之间都是一次一维的，又给了 10^16 的范围，疯狂暗示 :)
所以是可以用快速幂优化的
构造转移矩阵，需要 11 维，分别表示 [a, b, c 分别需要用到的数据], k, k^2, z^k, w^k, 1。然后同样地构造一个初始矩阵存起始值。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
__int128 mod = 998244353;
template <typename T>
struct Matrix {
T r, c;
std::vector<std::vector<T>> a;
Matrix(T n, T m)
: r(n), c(m), a(std::vector<std::vector<T>>(n, std::vector<T>(m))) {}
std::vector<T>& operator[](T i) { return a[i]; }
const std::vector<T>& operator[](T i) const { return a[i]; }
Matrix operator*(const Matrix& m) const {
Matrix ret(r, m.c);
for (T i = 0; i < r; i++)
for (T j = 0; j < m.c; j++) {
for (T k = 0; k < c; k++)
ret[i][j] =
(ret[i][j] + ((T)a[i][k] * m[k][j]) % mod) % mod;
}
return ret;
}
Matrix pow(T b) const {
Matrix A = *this, ret(r, r);
for (T i = 0; i < r; i++) ret[i][i] = 1;
for (; b; A = A * A, b >>= 1)
if (b & 1) ret = ret * A;
return ret;
}
};
int n, m, p, q, r, t, u, v, w, x, y, z;
signed main() {
cin >> n >> m >> p >> q >> r >> t >> u >> v >> w >> x >> y >> z;
mod = (__int128)m;
Matrix<__int128> A(11, 11);
Matrix<__int128> pre(1, 11);
pre.a = {{1, 3, 1, 3, 1, 3, 1, 1, 1, w, z}};
A.a = {{0, q, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, p, 0, 1, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, v, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, u, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, y, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 1, x, 0, 0, 0, 0, 0},
{0, r, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, t, 0, 0, 0, 1, 2, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 2, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0, w, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, z}};
Matrix<__int128> B = pre * A.pow(n - 2);
cout << "nodgd " << (long long)B[0][1] << endl
<< "Ciocio " << (long long)B[0][3] << endl
<< "Nicole " << (long long)B[0][5] << endl;
return 0;
}斜率优化
考虑 DP 式子 \(f_i = min(f_j + a_i * b_j)\)
对 i 转移有 j <= i，我们要找到能使 \(f_i\) 最小的值。
设 j = x, y 使 x < y。若有 \(f_x + a_i * b_x < f_y + a_i * b+y\)…. (1)
则 \(a_i \geq -((f_y-f_x)/(b_y - b_x))\) …………………….. (2)
也即 当满足(2)时，则取 x 更优，否则取 y 更优。
一般要求 \(a_i, b_i\) 均单调。
\(a_i\) 不单调二分，\(b_i\) 不单调平衡树。
除此之外，斜率优化还有另外一种更普适的做法。
可以考虑将要求极值化为一个函数
\(b = y - kx\)，我们将所有和要求的值相关的数都放在 b 上，将之前的值(j相关)放在 y 上，再把与 i, j 都相关的数放在 kx 上，并保证 k 是一个与前面的值无关的值(j无关)。
这样我们就可以将问题转化为一个笛卡尔坐标系上的问题。
接下来我们用一道例题详细的解释一下具体做法。
例题: P5785
f[i] = min ( f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]) )
f[i] = f[j] + t[i] * c[i] - t[i] * c[j] + s * c[n] - s * c[j];
斜率优化的基本方式：将要求极值的值作为截距 b
即 b = y - kx
套入上面的式子就是：
f[i] - t[i] * c[i] - s * c[n] = f[j] - (s + t[i]) * c[j]
即
\[\begin{array}{c}b = f[i] - t[i] * c[i] - s * c[n]\\y = f[j]\\k = s + t[i]\\x = c[j]\end{array}\]
相当于我们需要找到一组 (x, y) 使 b 最小。
那么我们 需要求得 min(f[j] - (s + t[i]) * c[j])，那么，我们找到一个 j，就可以得到 (x, y)
如果要让 y - kx 最小，在已知 k 的情况下，相当于一条可以上下移动，斜率为 k 的线，和一大堆 坐标为 (x, y) 的点。
其中每个点和 k 这个斜率可以求解出唯一的 b
现在我们的问题就转化为 让这条确定后的线的截距最小。
于是我们可以想象这样一个场景：
一条斜率为 k 的线去碰一大堆点，找到最下面的一个。(若是求 max 同理，可以考虑从上面靠或是直接取负转化为 min)
问题又可以转化为下凸壳。
而下凸壳是可以二分/单调队列求的。
这就是斜率优化的做法。