动态规划是一种常用的方法，通过记录“状态”将原问题划分为多个子问题从而使原问题得到解决。
树上 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) |
| 判断第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 都只有“一次”(即转移中不存在 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;
}