acm - 动态规划模板动态规划

71 阅读 0 评论 47 点赞

我是靠谱客的博主斯文秀发，最近开发中收集的这篇文章主要介绍acm - 动态规划模板动态规划，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

动态规划

思维导图：

数字三角形模型

每次只能向下走或者向右走。从起点走到终点。

题目给定一个 $n \times n$ 的矩阵，矩阵中的每个格子上有一个价值为 $w$ 的物品。给定起点 $(1, 1)$ 和终点 $(n, n)$ ，规定只能向下或者向右走。从起点出发两次，但同一个格子在两次路径中都经过的话，他的物品价值只会被累加一次。问两次路线，途径格子的物品的总价值最大是多少。

注意到每次走一步，横纵坐标的和都会加1.且知道横坐标，纵坐标，和两个坐标的和的任意两个就能知道另外一个。这就启示我们可以状态压缩。

另外两次行动可以看成一起同步行动。通过这样的想法就定义出 $d p [i] [j] [k]$ 表示 $a$ 路线当前横坐标为 $i$ ， $b$ 路线当前横坐标为 $j$ ，横纵坐标和为 $k$ 时的最大总价值。

状态只能由 $d p [i - 1] [j] [k - 1], d p [i] [j - 1] [k - 1], d p [i] [j] [k - 1], d p [i - 1] [j - 1] [k - 1]$ 这四者中转移过来。如果两点不重合，再加上 $a [i] [k - i], a [j] [k - 1]$ ，否则只要加上 $a [i] [j - i]$ 。

ll n;
ll a[15][15];
ll dp[15][15][30]; //横纵坐标为k=i+j时的最大值

bool check(int x, int y) {
    //是否非法
    if (x < 1 || x > n || y < 1 || y > n) return true;
    return false;
}

void solve() {
    n = read();
    while (1) {
        int u = read(), v = read(), w = read();
        if (!u && !v && !w) break;
        a[u][v] = w;
    }
    dp[1][1][2] = 0;
    //目标：dp[n][n][2n]
    for (int k = 3; k <= 2 * n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int ax = i, ay = k - i, bx = j, by = k - j;
                if (check(ax, ay) || check(bx, by)) continue;
                ll w1 = dp[ax - 1][bx - 1][k - 1], w2 = dp[ax][bx - 1][k - 1];
                ll w3 = dp[ax - 1][bx][k - 1],  w4 = dp[ax][bx][k - 1];
                ll w = max(max(w1, w2), max(w3, w4));
                if (ax == bx) 
                    //两个点是同一个点
                    dp[i][j][k] = max(dp[i][j][k], w + a[ax][ay]);
                else 
                    //两个点不是同一个点
                    dp[i][j][k] = max(dp[i][j][k], w + a[ax][ay] + a[bx][by]);
            }
        }
    }
    printf("%lldn", dp[n][n][2 * n]);
}

最长上升子序列模型

最长上升子序列：dp[i] = min{dp[j] + 1}, a[j] < a[i], j < i

最长公共子序列：dp[i] = min{dp[j] + 1}, a[j] = a[i], j < i

最长上升/下降子序列模板：

ll n;
ll a[MAXN];
ll dpl[MAXN], dpr[MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    dpl[1] = 1;
    for (int i = 2; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j < i; j++) 
            if (a[j] < a[i])
                mx = max(mx, dpl[j]);
        dpl[i] = mx + 1;
    }
    dpr[n] = 0;
    for (int i = n - 1; i; i--) {
        ll mx = -1;
        for (int j = n; j > i; j--) 
            if (a[j] < a[i])
                mx = max(mx, dpr[j]);
        dpr[i] = mx + 1;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dpl[i] + dpr[i]);
    printf("%lldn", ans);
}

经典的拦截导弹模型。

这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

求两个量，最多能拦截的导弹数和拦截所有导弹最少要配备的系统数

第一个问题求数组的最长非上升子序列，第二个问题求该数组最少能被几个最长下降子序列覆盖。

ll n;
ll a[MAXN];
ll dp1[MAXN];
ll dp2[MAXN];
void solve() {
    n = 0;
    ll tmp;
    while (scanf("%lld", &tmp) != EOF) {
        ++n;
        a[n] = tmp;
    }
    ll ans1 = 0;
    dp1[1] = 1;
    for (int i = 2; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j < i; j++) 
            if (a[j] >= a[i])
                mx = max(mx, dp1[j]);
        dp1[i] = mx + 1;
    }
    for (int i = 1; i <= n; i++) ans1 = max(ans1, dp1[i]);
    printf("%lldn", ans1);
    dp2[1] = 1;
    for (int i = 2; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j < i; j++) 
            if (a[j] < a[i])
                mx = max(mx, dp2[j]);
        dp2[i] = mx + 1;
    }
    ll ans2 = 0;
    for (int i = 1; i <= n; i++) ans2 = max(ans2, dp2[i]);
    printf("%lldn", ans2);
}

最长上升公共子序列

状态表示 $d p [i] [j]$ （集合）：考虑 $a$ 中前 $i$ 个数， $b$ 中前 $j$ 个数字，且当前以 $b [j]$ 结尾的子序列方案

状态表示 $d p [i] [j]$ （属性）： $ma x$

状态转移：

从 $a$ 中前 $i - 1$ 个数， $b$ 中前 $j$ 个数转移 $d p [i] [j] = ma x (d p [i] [j], d p [i - 1] [j])$
从 $a$ 中前 $i$ 个数， $b$ 中前 $k$ 个数且以 $b [k]$ 为结尾的子序列方案转移过来 $+1),kin[1,j-1],a_i=b_j$

每次遍历通过维护一个前缀最大值的方案可以省去一维的时间复杂度。

ll n;
ll a[MAXN];
ll b[MAXN];
ll dp[MAXN][MAXN]; //a前i个，b前j个，且以bj为结尾的最长上升公共子序列
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    ll mx = 0;
    for (int i = 1; i <= n; i++) {
        ll mx = 0;
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (a[i] == b[j]) dp[i][j] = max(mx + 1, dp[i][j]);
            if (b[j] < a[i]) mx = max(mx, dp[i - 1][j]);
                // for (int k = 1; k < j; k++) 
                //     if (b[j] > b[k])
                //         dp[i][j] = max(dp[i - 1][k] + 1, dp[i][j]);         
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[n][i]);
    printf("%lldn", ans);
}

背包模型

01背包求最值

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--) 
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= V; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= v[i])
            dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
    }
}

二维费用背包（就比01背包多开了一维）

for (int i = 1; i <= n; i++) 
    for (int j = V; j >= v[i]; j--) 
        for (int k = M; k >= m[i]; k--) 
            dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);

01背包求方案数（记得初始化）

ll n, V;
ll v[MAXN];
ll dp[MAXM];
void solve() {
    n = read(), V = read();
    dp[0] = 1;
    for (int i = 1; i <= n; i++) v[i] = read();
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] += dp[j - v[i]];
        }
    }
    printf("%lldn", dp[V]);
}

完全背包求最值（可以无限次选择）

遍历 $j$ 的时候从倒着遍历改成正的遍历就行了

完全背包求方案数。同求最值，改成正着遍历；注意初始化。

多重背包（单调队列优化）

物品数量有限，求最大价值。

价值 $w [i]$ ，体积 $v [i]$ ，个数 $s [i]$

令 $r = j$ $m o d$ $v_i$ ，也可以理解为完全背包下把当前物品选到不能再选后，剩下的余数。

可以推出公式 $d p (i, r) = d p (i - 1, r)$ 。

下述公式的第一个维度省略掉了，因为之和前一维有关

$dp(i,r) = dp_r$
$dp(i,r+v) = max(dp_{r+v},dp_r+w)$
$dp(i,r+2v) = max(dp_{r+2v},dp_{r+v}+w,dp_r+2w)$
…
$dp(i,r+sv)=max(dp_{r+sv},dp_{r+(s-1)v} +w,...,dp_r+sw)$ 滑动窗口已满
$dp(i,r+(s+1)v)=max(dp_{r+(s+1)v},dp_{r+sv}+w,...,dp_{r+v}+sw)$ 滑动窗口已满
…
$dp(i,j-2v)=max(dp_{j-2v},dp_{j-3v}+w,...,dp_{j-(s+2)v}+sw)$
$dp(i,j-v)=max(dp_{j-v},dp{j-2v}+w,...,dp_{j-(s+1)v}+sw)$
$dp(i,j)=max(dp_j,dp_{j-v}+w,...,dp_{j-sw}+sw)$

由此可见，滑动窗口大小为 $s [i] + 1$

通过该滑动窗口，就能在线性的时间里求出 $i$ 阶段中，所有满足 $j = r$ $m o d$ $v [i]$ 的 $d p (i, j)$

滑动窗口求最大值的实现，可以利用维护一个最大值单调递减的单调队列。

枚举所有的余数 $r$ 即可 $(0, v [i] - 1)$

不要忘记比较使得偏移量 $w$ 。

具体就是当前下标和最大值的下标之间差了 $x$ 个 $v [i]$ ，那么就要加上 $x$ 个 $w [i]$

时间复杂度 $O (n \times v)$ 空间复杂度 $O (n \times v)$ 滑动窗口长度 $s[i]+1 $

ll v[MAXN], w[MAXN], s[MAXN], V, n;
ll q[MAXM]; //存放体积
ll dp[2][MAXM]; //滚动数组
void solve() {
    n = read();
    V = read();
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        w[i] = read();
        s[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        for (int r = 0; r < v[i]; r++) { //枚举模数
            int hh = 1, tt = 0;
            for (int j = r; j <= V; j += v[i]) { //枚举模数恒为r的体积
                
                int now = i & 1;
                int pre = (i - 1) & 1;
                while (hh <= tt && dp[pre][q[tt]] + (j - q[tt]) / v[i] * w[i] <= dp[pre][j])
                    tt--; //保证队列单调递减
                q[++tt] = j;
                while (hh <= tt && j - q[hh] > v[i] * s[i]) 
                    hh++;  //加上当前要加入的元素，窗口元素大于s[i]+1，超过限制
                dp[now][j] = dp[pre][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    printf("%lldn", dp[n & 1][V]);
}

多重背包（二进制优化）

这个就好理解多了。所有数都可以被看成 $1+2+4+...+n-2^k+1$ 。这样的话 $s[i] = 1 + 2+4+...+2^{k-1},s[i]-(2^k-1)$ 。那么就可以当成若干个01背包中的物品了。体积是 $x \times v$ ，价值是 $x \times w$

时间复杂度 $O(n^2logs)$ ，其中 $s$ 表示所有物品的数量之和

ll n, V;
ll v[MAXN], w[MAXN], s[MAXN];
ll dp[MAXM];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        w[i] = read();
        s[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= s[i]; k *= 2) { //二进制枚举，分解成若干01背包
            ll tmpv = k * v[i];
            ll tmpw = k * w[i];
            for (int j = V; j >= tmpv; j--)
                dp[j] = max(dp[j - tmpv] + tmpw, dp[j]);
            s[i] -= k;
        }
        if (s[i]) { //最后的一部分，单独处理一下
            ll tmpv = s[i] * v[i];
            ll tmpw = s[i] * w[i];
            for (int j = V; j >= tmpv; j--)
                dp[j] = max(dp[j - tmpv] + tmpw, dp[j]);
        }
    }
    printf("%lldn", dp[V]);
}

混合背包

物品分三类：只能取一次，能取无限次，能取 $s [i]$ 次。使总价值最大。

针对三类物品做不同的状态转移即可，具体参考前文。

ll n, V;
ll v[MAXN], w[MAXN], s[MAXN];
ll dp[MAXN];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        v[i] = read();
        w[i] = read();
        s[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        if (!s[i]) //完全背包
            for (int j = v[i]; j <= V; j++)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        else if (s[i] == -1)  //01背包
            for (int j = V; j >= v[i]; j--) 
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        else {
            //多重背包
            for (int k = 1; k <= s[i]; k *= 2) {
                for (int j = V; j >= k * v[i]; j--)
                    dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
                s[i] -= k;
            }
            if (s[i])
                for (int j = V; j >= s[i] * v[i]; j--)
                    dp[j] = max(dp[j], dp[j - s[i] * v[i]] + s[i] * w[i]);
        }        
    }
    printf("%lldn", dp[V]);
}

一些变形

可以放置超过背包容量的物品，体积至少为xxx：

即当前背包预留的容量可以由负数转移过来（看成0）

memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) 
    for (int j = V; j >= 0; j--) 
        for (int k = M; k >= 0; k--) 
            dp[j][k] = min(dp[j][k], dp[max(0ll, j - v[i])][max(0ll, k - m[i])] + w[i]);

体积恰好为xxx

改变状态转移方程的前提条件。要么之前 $i - 1$ 时当前这个体积已经有方案了，要么只能有体积为 $0$ 的状态转移过来。

if (j >= v[i] && (j == v[i] || dp[i - 1][j - v[i]]) != 0)
   dp[i][j] = (dp[i][j] + dp[i - 1][j - v[i]]) % mod;

if (j == v[i] / 2 || dp[i - 1][j - v[i] / 2] != 0)
   dp[i][j] = (dp[i][j] + dp[i - 1][j - v[i] / 2]) % mod;

输出方案

有 $n$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ ，每件物品只能用一次。求解一种方案，使得选择的物品总体积小于 $V$ ，且总价值最大，输出字典序最小的方案。

做法就是先做一遍正常的背包 $D P$ ，然后从目标状态倒退回初始状态的整个转移路径

伪代码：

int v = V;  // 记录当前的存储空间

// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件) {
  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

题目还要求了字典序最小。在倒退转移方程时，如果碰到物品既可以选也可以不选，优先的选项是选择该物品。因此，背包 $D P$ 是倒过来 (从n到1)，然后再从 $1$ 倒推会 $n$ 找出路径。这样，如果出现分叉情况是，就优先选当前物品即可。

ll n, V;
ll dp[MAXN][MAXN];
ll v[MAXN], w[MAXN];
int path[MAXN], cnt = 0; //保存路径

void dfs(int i, ll j) {
    if (i == n + 1) return;
    if (j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]) {
        path[++cnt] = i;
        dfs(i + 1, j - v[i]); //选择当前物品
    }
    else
        dfs(i + 1, j); //不选择当前物品
}

void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i + 1][j]; //状态复制
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
        }
    }       
    // for (int i = 1, j = V; i <= n; i++) {
    //     if (j >= v[i] && dp[i + 1][j - v[i]] + w[i] == dp[i][j]) {
    //         //选了当前的物品，把他扔掉
    //         path[++cnt] = i;
    //         j -= v[i];
    //     }
    // }       
    dfs(1, V);
    for (int i = 1; i <= cnt; i++) printf("%d ", path[i]);
}

分组背包+输出方案

题目：总公司拥有 $M$ 台设备，准备分给下属的 $n$ 个分公司。第 $i$ 家公司分到 $j$ 台机器后，所获得的收益为 $w_{ij}$ 。求一种分配方案，使得总收益最大，输出该方案。

分析：每家公司都可以看成一个物品组，又因为每家公司最终能够被分配的机器数量是固定的，因此对于分给第 $i$ 个公司的不同机器数量可以分别看做是一个物品组内的物品。

物品含义：分为第 $i$ 个公司 $k$ 台机器
物品体积： $k$
该物品 $k$ 的价值： $w_{ik}$

ll n, m;
ll a[25][25];
ll dp[25][25];
int path[25], cnt;

void dfs(int now, int v) {
    if (!now) return; //所有物品都选完了
    for (int i = 0; i <= m; i++) {
        if (v >= i && dp[now][v] == dp[now - 1][v - i] + a[now][i]) {
            path[now] = i;
            dfs(now - 1, v - i);
            return; //同一组内只能选一个，选完直接return
        }
    }
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j]; //状态转移，先假设不选当前组内物品
            for (int k = 1; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + a[i][k]);
            }
        }
    }
    printf("%lldn", dp[n][m]);
    // for (int i = n, j = m; i >= 1; i--) {
    //     for (int k = 0; k <= m; k++) {
    //         if (j >= k && dp[i][j] == dp[i - 1][j - k] + a[i][k]) {
    //             j -= k;
    //             path[i] = k;
    //             break; //同一组内只能选一个，选完后就break掉
    //         }
    //     }
    // }
    dfs(n, m);
    for (int i = 1; i <= n; i++) printf("%d %dn", i, path[i]);
}

这是分组背包最裸的模板

ll n, V;
ll v[MAXN][MAXN], w[MAXN][MAXN], dp[MAXN][MAXN], cnt[MAXN];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        cnt[i] = read();
        for (int j = 1; j <= cnt[i]; j++)
            v[i][j] = read(), w[i][j] = read();
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= cnt[i]; k++) {
                if (j >= v[i][k])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    printf("%lldn", dp[n][V]);
}

压缩成一维后：

for (int i = 1; i <= n; i++) //枚举物品组
    for (int j = V; j >= 0; j--) //枚举给当前物品组分配的体积
        for (int k = 1; k <= cnt[i]; k++) //枚举物品
            if (j >= v[i][k]) 
                dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);         
printf("%lldn", dp[V]);

01背包求最优方案数

思路就是先求一次 $d p$ ，再搞一次逆推方案。

空间不优化写法：

ll n, V;
ll v[MAXN], w[MAXN];
ll mx;
ll dp[MAXN][MAXN]; //最优价值
ll cnt[MAXN][MAXN]; //方案数量
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();   
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    } 
    cnt[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            if (dp[i][j] == dp[i - 1][j])
                cnt[i][j] = (cnt[i][j] + cnt[i - 1][j]) % mod;
            if (j >= v[i] && dp[i - 1][j - v[i]] + w[i] == dp[i][j])
                cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - v[i]]) % mod;
        }
    }
    ll ans = 0;
    for (int i = 0; i <= V; i++) 
        if (dp[n][i] == dp[n][V])
            ans = (ans + cnt[n][i]) % mod;
    printf("%lldn", ans);
}

空间优化成一维后：

ll n, V;
ll v[MAXN], w[MAXN];
ll mx;
ll dp[MAXN];
ll cnt[MAXN];
void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) v[i] = read(), w[i] = read();  
    cnt[0] = 1; 
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            ll tmp = max(dp[j], dp[j - v[i]] + w[i]);
            ll now = 0;
            if (tmp == dp[j - v[i]] + w[i])
                now = (now + cnt[j - v[i]]) % mod;
            if (tmp == dp[j])
                now = (now + cnt[j]) % mod;
            dp[j] = tmp, cnt[j] = now;
        }
    } 
    ll ans = 0;
    for (int i = 0; i <= V; i++) 
        if (dp[i] == dp[V])
            ans = (ans + cnt[i]) % mod;
    printf("%lldn", ans);
}

有依赖的背包问题（树上背包）

有 $n$ 件物品和一个体积为 $V$ 的背包。第 $i$ 件物品的体积为 $v [i]$ ，价值为 $w [i]$ ，每件物品有一个父节点物品 $p [i]$ ，如果想选第 $i$ 件物品，就必须选他的父节点 $p [i]$ 。求能选出的最大价值。

首先，这种依赖关系类似于树中的父节点和子节点，于是用树形DP来做。

考虑到根据方案划分的话，有 $2^x$ 种状态，显然存不下。因此考虑根据体积来划分，枚举每棵子树的共用体积。（这个过程有点像分组背包）

状态表示集合：考虑第 $i$ 个物品为根节点的子树，且选上 $i$ ，选法的总体积不超过 $j$ 的方案。

状态表示属性：方案的总价值最大 $M a x$

状态计算：

时间复杂度 $O (n \times V \times V)$

ll n, V;
ll v[MAXN], w[MAXN];
ll dp[MAXN][MAXN];
int root;

void dfs(int now, int pre) {
    //先枚举所有体积小于等于V-v[now]的所有子节点们能获得的最大价值
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to; //枚举物品组
        if (to == pre) continue;
        dfs(to, now); //用子节点更新父节点，树形DP，从下往上算
        for (int j = V - v[now]; j >= 0; j--) //所有子节点的体积和 实测j=V开始也行，因为这个状态最终会被废弃（覆盖）掉
            for (int k = 0; k <= j; k++) //枚举物品，对应被分配到的体积
                dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[to][k]);
    }
    //最后选上当前的根节点now物品
    for (int j = V; j >= v[now]; j--) dp[now][j] = dp[now][j - v[now]] + w[now];
    for (int j = 0; j < v[now]; j++) dp[now][j] = 0; //清空没选上now的所有状态
}

void solve() {
    n = read(), V = read();
    for (int i = 1; i <= n; i++) {
        int fa;
        v[i] = read(), w[i] = read(), fa = read();
        if (fa == -1) root = i;
        else add_edge(fa, i), add_edge(i, fa);
    }
    dfs(root, -1);
    printf("%lldn", dp[root][V]);
}

亿点点细节：枚举子节点的共用体积 $j$ 时要倒着枚举，因为确保当前一层只被更新一次。根节点物品最后才计算，因为这样能防止被覆盖掉。体积小于 $v [n o w]$ 的要被清零，因为这是有依赖关系的，子节点生效的前提条件是选了当前父节点。

有依赖的背包问题（体积和价值在边上）

给定一颗含有 $n$ 个节点的树，树根编号为 $1$ ，且树上的每一条边有一个边权 $w [i]$ 。要求保留树中的 $m$ 条边，使得树根所在的连通块的所有边边权之和最大。

定义状态 $d p [i] [j]$ ，以 $i$ 为根节点的子树，包含 $i$ 的连通块的边数不超过 $j$ 的方案。

当点作为体积时，第一重循环的 $j$ 可以取 $V - v [n o w]$ 也可以取 $V$ ，因为根据状态的定义，必须选当前节点的体积，另外多枚举的部分在之后会被覆盖掉。当边作为体积时， $j$ 只能从 $V$ 开始而不是 $V - 1$ ，因为假设当前是根节点的话就少枚举了。

$k$ 则对应决策方案，为某个子树被分到的体积。枚举 $k$ 的时候最大到 $j - 1$ ，是因为如果计算该子树对父节点的贡献，必须保留他到父节点的边。

代码可以和上一道好好对比

ll n, m;
struct EDGE {
   int to, next, val;
}edge[MAXM];
int head[MAXN], tot;
void add(int from, int to, int val) {
   edge[++tot].to = to, edge[tot].val = val, edge[tot].next = head[from], head[from] = tot;
}
ll dp[MAXN][MAXN];

void dfs(int now, int pre) {
   for (int i = head[now]; i; i = edge[i].next) {
       int to = edge[i].to;
       int val = edge[i].val;
       if (to == pre) continue;
       dfs(to, now);
       for (int j = m; j >= 0; j--) { //体积
           for (int k = 0; k < j; k++) { //决策，预留一条连向父节点的边
               dp[now][j] = max(dp[now][j - k - 1] + dp[to][k] + val, dp[now][j]);
           }
       }        
   }
}

void solve() {
   n = read(), m = read();
   for (int i = 1; i < n; i++) {
       int u = read(), v = read(), w = read();
       add(u, v, w);
       add(v, u, w);
   }
   dfs(1, -1);
   printf("%lldn", dp[1][m]);
}

有依赖的背包问题，根节点不止一个（森林）

可以利用图论中超级源点中的思想，建一个虚拟源点连接所有的根节点，这样森林就变成了一棵树。然后定义这个虚拟源点的体积为 $1$ ，或者任何正数，在总体积中加上虚拟源点的体积正常做树上背包即可。例题中所有节点体积都为 $1$ 。

int n, V;
int dp[MAXN][MAXN];
int w[MAXN];

void dfs(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs(to, now);
        for (int j = V; j >= 0; j--) //枚举体积 
            for (int k = 0; k <= j; k++)
                dp[now][j] = max(dp[now][j - k] + dp[to][k], dp[now][j]);
    }
    for (int j = V; j >= 1; j--)
        dp[now][j] = dp[now][j - 1] + w[now];
    dp[now][0] = 0;
}

void solve() {
    n = read(), V = read();
    V++;
    for (int i = 1; i <= n; i++) {
        int fa;
        fa = read(), w[i] = read();
        add(fa, i), add(i, fa);
    }
    dfs(0, -1);
    printf("%dn", dp[0][V]);
}

有依赖的背包问题（分组背包）

一共有 $n$ 个物品和 $V$ 体积的背包。

物品之间可能存在依赖关系，每个物品体积为 $v [i]$ , 价值为 $w [i]$ ，依赖的父亲物品为 $p [i]$ ，每个物品只能被购买一次。

求一种购买方案，使得总花费不超过 $V$ ，且总价值最大。

注意，每个父亲的儿子不超过两个，且儿子不会再有儿子。

如果按照体积划分，时间复杂度 $O (n \times V \times V)$ 就会超时了。

注意到每个主件的附属品不超过两个，且附属品不会再有附属品。因此可以采用分组背包对本题的状态进行划分。具体做法就是用类似于状态压缩的方法，二进制枚举所有情况，每种组合对应一个物品组内的一个物品。时间复杂度 $2^2 times V)$

ll V, n;
ll v[MAXN], w[MAXN];
bool isfa[MAXN]; //判断是否为主件
vector<int> g[MAXN];
ll dp[MAXM];

void init() {
    for (int i = 1; i <= n; i++) g[i].clear(), isfa[i] = false;
}

void work(int now, ll j) {
    int len = g[now].size(); //当前分组内的物品
    //类似于状态压缩的方法，因为数量不多，直接二进制遍历所有的状态，相当于枚举所有的方案
    for (int st = 0; st < (1 << len); st++) {
        int sum_v = v[now];
        ll sum_w = w[now];
        for (int i = 0; i < len; i++) {
            if (st >> i & 1) 
                sum_v += v[g[now][i]], sum_w += w[g[now][i]]; 
        }
        if (sum_v <= j)
            dp[j] = max(dp[j], dp[j - sum_v] + sum_w);
    }
}

void solve() {
    V = read(), n = read();
    init();
    for (int i = 1; i <= n; i++) {
        int fa;
        v[i] = read(), w[i] = read(), fa = read();
        w[i] = w[i] * v[i];
        if (fa) g[fa].pb(i);
        else isfa[i] = true;
    }
    for (int i = 1; i <= n; i++)
        if (isfa[i]) //枚举物品组
            for (int j = V; j >= v[i]; j--) //枚举分配给物品组的体积
                work(i, j);
    printf("%lldn", dp[V]);
}

状态机模型

对于状态机而言，如果上一个状态合法，而且可以转移到当前状态，那么这个转移合法。状态机的转移，就类似于图中两个点连边。主要是判断这个转移是否合法，如果合法，就添加边。

以没有上司的舞会这题为例，当前上司不参加对应两种状态：其下属参加和下属不参加都是合法的。当前上次参加对应两种状态：其下属参加和下属不参加，那么第一种状态就是非法的。

题目： 街道上有 $n$ 家店铺，第 $i$ 家店铺的财产是 $a [i]$ 。小偷不能连续偷两个相邻的店铺。求小偷能获得的最大财产。

如果要偷第 $i$ 家店铺，那么第 $i - 1$ 个店铺不能被偷，因为这是非法的，此时

$d p [1] [i] = ma x (d p [1] [i - 2], d p [0]) + a [i]$

否则的话

$d p [0] [i] = ma x (d p [1] [i - 1], d p [0] [i - 1])$

ll n;
ll a[MAXN];
ll dp[2][MAXN]; //1表示抢劫i，0表示不抢劫i
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    dp[0][0] = 0; dp[1][0] = 0;
    dp[0][1] = 0, dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[0][i] = max(dp[1][i - 1], dp[0][i - 1]);
        dp[1][i] = max(dp[0][i - 1] + a[i], dp[1][i - 2] + a[i]);
    }
    printf("%lldn", max(dp[0][n], dp[1][n]));
}

题目： 给定一个长度为 $n$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。最多可以完成 $k$ 笔交易，计算所能获取的最大利润。一次买入一次卖出即为一笔交易，且不能同时产生多笔交易。

定义状态 $d p [i] [j] [k]$ 表示前 $i$ 天，进行了 $k$ 笔交易，状态 $j$ 为 $0$ （空仓）或状态 $j$ 为 $1$ （持仓）时的最多利润。

若当前这一天空仓，要么前一天也空仓，要么当前这一天把股票卖出了（此时注意交易数需要减一）

若当前这一天持仓，要么前一天也持仓，要么当前这一天买入了股票

ll n, k;
ll a[MAXN];
ll dp[2][2][105]; //前i天，交易k次，状态为 0（空仓）1（持仓）
void solve() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(dp, ~0x3f, sizeof dp); //交易一次以上的赋为负无穷
    for (int i = 0; i <= n; i++) dp[i][0][0] = 0; //没有交易过的赋为0
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int now = i & 1;
        int pre = 1 - now;
        for (int j = 0; j <= k; j++) {
            //若持仓，要么前一天也持仓，要么当前这一天买入股票
            dp[now][1][j] = max(dp[pre][1][j], dp[pre][0][j] - a[i]);
            //若空仓，要么前一天也空仓，要么当前这一天卖出股票
            if (!j) 
                dp[now][0][j] = 0;
            else
                dp[now][0][j] = max(dp[pre][0][j], dp[pre][1][j - 1] + a[i]);
        }
    }
    ll ans = -INF;
    for (int i = 0; i <= k; i++) ans = max(ans, dp[i & 1][0][i]);
    printf("%lldn", ans);
}

同样，修改条件。去掉了交易次数的限制，但是新增了一个状态：冷冻期。在卖出股票后进入一天冷冻期，在这期间内不能买入股票。

状态机图示：

空仓时，要么前一天也空仓，要么前两天卖出即前一天是冷冻期。

持仓时，要么前一天也持仓，要么前一天空仓当前买入

冷冻期时，前一天持仓前一天卖出

最后一天要么是空仓状态要么是冷冻期，比较一下取最大即可。

ll dp[2][3];
ll n;
ll a[MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    //空仓，0，要么前一天空仓，要么前两天卖出即前一天冷冻
    //持仓, 1，要么前一天持仓，要么前一天空仓后当前买入
    //冷冻，2，前一天持仓前一天卖出
    dp[0][1] = -INF, dp[0][2] = -INF; //非法状态
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int now = i & 1;
        int pre = 1 - now;
        dp[now][0] = max(dp[pre][0], dp[pre][2]);
        dp[now][1] = max(dp[pre][1], dp[pre][0] - a[i]);
        dp[now][2] = dp[pre][1] + a[i];
    }
    printf("%lldn", max(dp[n & 1][0], dp[n & 1][2]));
}

**题目：**给定一个长度为 $m$ 的字符串T和一个整数 $n$ ，现需设计一个密码 $S$ 满足 $S$ 仅有长度为 $n$ 的小写字母组成且 $S$ 不包含子串 $T$ 。问有几种方案。

只有密码的最大后缀子串为 $m$ 时方案才不合法，也就是说最大后缀子串长度小于 $m$ 时都是合法方案。定义 $d p [i] [j]$ 表示构造一个长度为 $i$ 的密码，且后缀与模式串匹配的最大长度为 $j$ 的方案数量。根据上面的结论，可以得出 $an s = \sum d p [n] [j], 0 \leq j < m$ 。可以证明这是不重不漏的。这时一共有 $m + 1$ 个状态，其中最后一个状态即匹配长度为 $m$ 的状态为非法状态。

状态机大概长这样

// kmp匹配过程
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && s[i] != p[j+1]) j = ne[j]; //如果不能j往前走，就退一步
        if(s[i] == p[j+1]) j++;
        if(j == n)
        {
            // 匹配成功
            printf("%d ",i-n);
            j = ne[j]; 
        }
    }

若下一个字母能直接匹配上，那么 $d p [i + 1] [j + 1] + = d p [i] [j]$

若下一个字母不能匹配上，跳到了 $p os = n x t [j]$ 。如果 $T [p os + 1] = c h$ ，那么 $d p [i + 1] [l e n] + = d p [i] [j]$ ， $l e n$ 表示匹配的长度。

若 $n x t [j] \neq = p os$ ，表示匹配不上，即匹配长度为 $0$ 。那么， $d p [i + 1] [0] + = d p [i] [j]$

char s[MAXN]; //模式串
int n;
int nxt[MAXN];
ll dp[MAXN][MAXN];
void solve() {
    n = read();
    scanf("%s", s + 1);
    int m = strlen(s + 1);
    for (int i = 2, j = 0; i <= m; i++) { //求kmp的next数组
        while (j && s[i] != s[j + 1]) j = nxt[j];
        if (s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) { //枚举匹配的最大后缀
            for (char ch = 'a'; ch <= 'z'; ch++) {
                int len = j; //计算枚举到第i+1个字符后，后缀匹配的最大长度
                while (len && s[len + 1] != ch) len = nxt[len];
                if (s[len + 1] == ch) len++; //能够匹配上
                if (!len) //第i+1为ch时，不能匹配上
                    dp[i + 1][0] = (dp[i + 1][0] + dp[i][j]) % mod;
                else //第i+1为ch时，能够匹配上，那么最大长度加1
                    dp[i + 1][len] = (dp[i + 1][len] + dp[i][j]) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < m; i++) ans = (ans + dp[n][i]) % mod;
    printf("%lldn", ans);
}

状态压缩模型

大体分两种，棋盘式（在棋盘上放棋子避免他们互相攻击，判断连通性），集合式（每个元素在不在集合里面）。核心就是用一串二进制数暴力压缩掉一维的数。

棋盘类

题目：

在 $n \times n$ 的棋盘上放 $k$ 个国王。国王可攻击相邻的 $8$ 个格子，求使得这 $k$ 棋子无法互相攻击的方案总数。

用长度为 $n$ 的二进制数来表示一行的状态。这样当 $（ s t >> i ） = 1$ 时，即表示当前这位上存在棋子，否则不存在。这样就可以预处理出单独一行的所有合法状态和两行之间的所有合法状态。定义 $d p [i] [k] [j]$ 为第 $i$ 行，放置了 $k$ 个国王，当前行状态为 $j$ 时的方案数量。初始化 $d p [0] [0] [0] = 1$

转移方程： $d p [i] [k] [j] = \sum d p [i - 1] [k - c n t [j]] [p re]$ ， $p re$ 表示上一行的合法状态。

int n, m;
ll dp[2][105][(1 << MAXN) + 5];
int cnt[(1 << MAXN)];
vector<int> v; //存储当前行的合法状态
vector<int> g[(1 << MAXN) + 5]; //存储行与行之间的合法状态
bool judge(int st) { //行内判断合法状态
    if (st & st << 1) return false;
    if (st & st >> 1) return false;
    return true;
}

bool work(int now, int pre) { //行与行之间判断合法状态
    if (now & pre) return false;
    if (now & pre >> 1) return false;
    if (now & pre << 1) return false;
    return true;
}

int sum(int st) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int u = st >> i & 1;
        ans += u;
    }
    return ans;
}

void solve() {
    n = read(), m = read();
    vector<int> v;
    for (int st = 0; st < (1 << n); st++) 
        if (judge(st))
            v.pb(st), cnt[st] = sum(st);
    for (int now : v) 
        for (int pre : v)
            if (work(now, pre))
                g[now].pb(pre);
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) 
        for (int k = 0; k <= m; k++) 
            for (int now : v) {
                dp[i & 1][k][now] = 0; //先清零因为是+=，滚动数组之前的结果有影响
                for (int pre : g[now]) 
                    if (cnt[now] <= k)
                        dp[i & 1][k][now] += dp[(i - 1) & 1][k - cnt[now]][pre];           
            }
    ll ans = 0;            
    for (int st : v) ans += dp[n & 1][m][st];
    printf("%lldn", ans);
}

题目： 给定一个 $n \times m$ 的矩阵，矩阵中 $H$ 表示不能放置棋子，标 $P$ 表示可以放置棋子。棋子的攻击方向为上下左右，距离两个单位。求出最大的棋子放置数量，使得棋子之间不会互相攻击。

加入了图的限制。不过可以用类似的方式，把矩阵每一层的状态也用二进制来压缩存储，注意：用0表示该位置能放棋子，1表示不能放 。这样只需要把当前这一层的状态 $s t$ 和矩阵这一层的状态做与运算。如果结果为 $0$ ，表示合法；若为 $1$ ，说明放置棋子的位置与不能放置棋子的位置发生重叠，该状态非法。然后可以发现，与之前的 $w or k$ 函数所表示的含义是一样的，于是乎就可以共用了。

若只压缩一层的信息，只能保证上一层是合法的，不能保证上上层摆放的棋子一定攻击不到当前这层。所以状态定义的时候多加一位，然后通过预处理的邻接矩阵枚举合法的第 $i - 2$ 层状态进行转移即可。

状态表示 $d p [i] [j] [k]$ ：考虑前 $i$ 层且第 $i$ 层状态为 $j$ ，第 $i - 1$ 层状态为 $k$ 的方案。
状态属性：该方案能够放置棋子的最大个数
状态计算： $d p [i] [j] [k] = ma x$ { $d p [i - 1] [k] [p re]$ } + $c n t [j]$ ， $p re$ 表示能够与 $k$ 和 $j$ 同时合法存在于三行中的所有状态

char s[105][15];
int a[105];
int n, m;
vector<int> v;
vector<int> g[(1 << 10) + 5];
int cnt[(1 << 10) + 5];
ll dp[2][(1 << 10) + 5][(1 << 10) + 5];
bool judge(int st) {
    if (st & (st >> 1) || st & (st >> 2)) return false;
    if (st & (st << 1) || st & (st << 2)) return false;
    return true; 
}

bool work(int now, int pre) {
    if (now & pre) return false;
    return true;
}

int sum(int st) {
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int u = st >> i & 1;
        ans += u;
    }
    return ans;
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i]);
    for (int i = 1; i <= n; i++) {
        int ans = 0;
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'P') //山地
                {}
            else //平原
                ans += (1 << j);
        }
        a[i] = ans;
    }
    for (int st = 0; st < (1 << m); st++) 
        if (judge(st)) 
            v.pb(st), cnt[st] = sum(st);
    for (int now : v) 
        for (int pre : v)
            if (work(now, pre))
                g[now].pb(pre);
    for (int i = 1; i <= n; i++) 
        for (int now : v) 
            for (int PRE : g[now]) {
                dp[i & 1][now][PRE] = 0; //清空滚动数组之前的结果
                if (work(now, a[i])) //当前行合法
                    for (int pre : g[PRE]) //枚举上上行
                        if (work(now, pre)) //若上上行和当前和不会互相攻击
                            dp[i & 1][now][PRE] = max(dp[i & 1][now][PRE], dp[(i - 1) & 1][PRE][pre] + cnt[now]);
            }          
    ll ans = 0;
    for (int now : v) 
        for (int pre : g[now]) 
            ans = max(ans, dp[n & 1][now][pre]);   
    printf("%lldn", ans);
}

上面只管了当前这一行与图的合法关系。因为之前行若与图之间不合法的话，最大值一定为 $0$ （因为有个 $i f$ 来判断），对答案无影响。如果是算方案数类型的题目也没影响，因为一开始会对所有的状态清零，若某一状态与图之间的关系非法，那么该状态的方案数也一定为 $0$ ，对答案也没有影响。代码写起来长这样：

dp[0][0] = 1;
for (int i = 1; i <= n; i++) 
    for (int now : v) {
        dp[i & 1][now] = 0;
        if (work(now, a[i])) 
            for (int pre : g[now]) 
                dp[i & 1][now] = (dp[i & 1][now] + dp[(i - 1) & 1][pre]) % mod;
    }

更加易懂（但是慢）的代码：

for (int i = 1; i <= n; i++)
    for (int j = 0; j < state.size(); j++)
        for (int k = 0; k < state.size(); k++)
            for (int u = 0; u < state.size(); u++) {
                int a = state[j], b = state[k], c = state[u];
                if (a & b | a & c | b & c) //能互相攻击
                    continue;
                if (g[i] & b | g[i - 1] & a) //在不该放置棋子的地方放了棋子
                    continue;
                f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
            }

集合类

题意： 愤怒的小鸟模型。给出 $n$ 个猪的坐标，问最少几条抛物线能把猪全部打死（抛物线开口向下，且一定从坐标原点开始）

根据简单数学知识，在本题中，两头猪确定一条抛物线，所以最多有 $n^2$ 条抛物线。

预处理 $se g [i] [j]$ 数组，表示编号为 $i$ 的猪和编号为 $j$ 的猪所在的抛物线。属性表示为这个抛物线可消灭的猪的编号，二进制表示。如100111，表示 $1, 2, 3, 6$ 的猪能被当前这条抛物线杀死。

状态表示 $d p [i]$ ， $i$ 这个状态（二进制表示）下最少要用多少条抛物线击杀所有猪。属性为最小值。

状态计算：找到 $i$ 状态下没有被消灭的猪的其中一个编号 $x$ ，枚举可消灭它的抛物线 $se g [x] [j]$ 并更新状态。

$d p [i ∣ se g [x] [j]] = min (d p [i ∣ se g [x] [j]], d p [i] + 1)$ 。注意，这里只需枚举其中任意一个就行。因为先杀死哪头猪对结果没有关系，也就是这些抛物线选择的先后顺序不重要，且之后一定不会漏

int seg[MAXN][MAXN]; //所有抛物线杀死猪的情况，1表示被杀死
pdd node[MAXN];
ll dp[1 << MAXN];
int n, m;

int cmp(double a, double b) {
    if (fabs(a - b) < 1e-8) return 0; //相同
    if (a > b) return 1; //a大于b
    if (a < b) return -1; //a小于b
}

void solve() {
    n = read(), m = read();
    for (int i = 0; i < n; i++) scanf("%lf%lf", &node[i].first, &node[i].second);
    memset(seg, 0, sizeof seg);
    for (int i = 0; i < n; i++) {
        seg[i][i] = 1 << i; //一条直线
        for (int j = 0; j < n; j++) {
            //两个点确定一条抛物线
            double x = node[i].first, y = node[i].second;
            double xx = node[j].first, yy = node[j].second;
            double a = (y / x - yy / xx) / (x - xx);
            double b = (y / x - a * x);
            if (cmp(a, 0.0) != -1) continue; //抛物线开口向上，舍去
            for (int k = 0; k < n; k++) {
                double u = node[k].first, v = node[k].second;
                if (cmp(a * u * u + b * u, v) == 0) 
                    seg[i][j] += 1 << k; //能够杀死这头猪
            }

        }
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int st = 0; st < (1 << n) - 1; st++) {
        int pos = -1;
        for (int i = 0; i < n; i++)
            if (!(st >> i & 1))
                pos = i;
        for (int i = 0; i < n; i++) {
            int nxt = seg[pos][i] | st;
            dp[nxt] = min(dp[nxt], dp[st] + 1);
        }
    }
    printf("%lldn", dp[(1 << n) - 1]);
}

区间DP模型

环形石子DP

ll n;
ll a[MAXN];
ll mx[MAXN][MAXN], mn[MAXN][MAXN];
ll sum[MAXN];
void solve() {
    n = read();
    for (int i = 1; i < n; i++) {
        a[i] = read();
        a[i + n] = a[i];
    }
    a[n] = read();
    ll N = 2 * n - 1;
    for (int i = 1; i <= N; i++) sum[i] = sum[i - 1] + a[i];
    memset(mn, 0x3f, sizeof mn);
    memset(mx, ~0x3f, sizeof mx);
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= N; l++) {
            if (l == r) {
                mn[l][r] = 0;
                mx[l][r] = 0;
            }
            else {
                for (int k = l; k < r; k++) {
                    //[l,k] [k+1,r]
                    mx[l][r] = max(mx[l][k] + mx[k + 1][r] + sum[r] - sum[l - 1], mx[l][r]);
                    mn[l][r] = min(mn[l][k] + mn[k + 1][r] + sum[r] - sum[l - 1], mn[l][r]);
                }
            }
        }
    }
    ll MN = INF, MX = -INF;
    for (int i = 1; i <= n; i++) {
        MN = min(MN, mn[i][i + n - 1]);
        MX = max(MX, mx[i][i + n - 1]);
    }
    printf("%lldn%lldn", MN, MX);
}

**题目：**给定一个含有 $n$ 个节点的二叉树的中序遍历序列中每个节点的权值。定义一棵子树的分数为左子树的分数 $\times$ 右子树的分数 $+$ 根节点的权值。规定空树的分数为 $1$ 。求一种方案，使得分数最大。

区间内枚举根节点的位置即可

ll n;
ll a[MAXN];
ll dp[MAXN][MAXN];
int rt[MAXN][MAXN];

void dfs(int now, int l, int r) {
    if (l > r) return;
    printf("%d ", now);
    dfs(rt[l][now - 1], l, now - 1);
    dfs(rt[now + 1][r], now + 1, r);
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(dp, ~0x3f, sizeof dp);
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= n; l++) {
            if (len == 1) {
                dp[l][r] = a[l];
                rt[l][r] = l;
            }
            else {
                for (int k = l; k <= r; k++) { //枚举一段区间内的根节点
                    ll lscore = k == l? 1ll: dp[l][k - 1];
                    ll rscore = k == r? 1ll: dp[k + 1][r];
                    ll score = lscore * rscore + a[k];
                    if (score > dp[l][r]) {
                        dp[l][r] = score;
                        rt[l][r] = k;
                    }
                }   
            }
        }
    }
    printf("%lldn", dp[1][n]);
    dfs(rt[1][n], 1, n);
}

题目： 给出一个 $1 \times n$ 的空间玩 $2048$ 。每次可以合并相邻两个数，合并后的数值加一。求最后序列中的最大值。

考察了完全合并，即区间内所有数必须合并才能进行状态转移。

ll dp[MAXN][MAXN];
ll n;
ll a[MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    ll ans = 0;
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= n; l++) {
            if (l == r)
                dp[l][r] = a[l], ans = max(ans, a[l]);
            else {
                for (int k = l; k < r; k++) {
                    int lmx = dp[l][k];
                    int rmx = dp[k + 1][r];
                    if (lmx == 0 || rmx == 0 || lmx != rmx) continue;
                    
                    dp[l][r] = lmx + 1;
                    ans = max(ans, dp[l][r]);
                }
            }
        }
    }
    printf("%lldn", ans);
}

题目： 给出以序列，每个可以删除一段连续的回文串，问最少几次操作能全删光。

长度为 $1$ ， $d p [l] [r] = 1$
长度为 $2$
- 相同， $d p [l] [r] = 1$
- 不相同， $d p [l] [r] = 2$
长度大于 $2$
- 首尾不相同 $d p [l] [r] = min (d p [l] [k], d p [k + 1] [r])$
- 首尾相同，取最小值时加个 $d p [i + 1] [j - 1]$

ll n;
ll a[MAXN];
ll dp[MAXN][MAXN];
void solve() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    memset(dp, 0x3f, sizeof dp);
    for (int len = 1; len <= n; len++) {
        for (int l = 1, r; r = l + len - 1, r <= n; l++) {
            if (len == 1)
                dp[l][r] = 1;
            else if (len == 2) {
                if (a[l] == a[r])
                    dp[l][r] = 1;
                else
                    dp[l][r] = 2;
            }
            else {
                for (int k = l; k < r; k++)
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
                if (a[l] == a[r])
                    dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
            }
        }
    }
    printf("%lldn", dp[1][n]);   
}

树形DP模型

树上背包参考前面的有依赖的背包问题部分

核心就是先一路递归下去直到叶子节点，然后用已知的子节点状态更新父节点状态。当需要再用父节点状态来更新子节点时，用换根DP

求树的直径

一共有三种路径：

以子树中的某个节点作为起点，以它作为终点
以子树中的某个节点作为起点，以子树中的某个节点作为终点
以子树中的某个节点作为起点，以非其子树中的某个节点作为终点

第一种情况可以找出最长路径，第二种情况可以顺便找最长路径的时候找出次长路径，第三种情况可以归类于某个祖先节点的最长路径和次长路径。

所以树形DP维护两个东西，以节点 $i$ 为根的子树中，以某个节点到 $i$ 的最长路径和次长路径。

ll ans1 = -INF, ans2 = -INF, ans;
ll n;

ll dfs(int now, int pre) {
    ll mx = 0;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        ll tmp = val + dfs(to, now);
        mx = max(mx, tmp);
        
        if (tmp > ans1) {
            ans2 = ans1;
            ans1 = tmp;
        }
        else if (tmp <= ans1 && tmp > ans2) {
            ans2 = tmp;
        }
        ans = max(ans, ans1 + ans2);
    }
    return mx;
}

void solve() {
    n = read();
    for (int i = 1; i < n ; i++) {
        ll u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u ,w);
    }
    dfs(1, -1);
    printf("%lldn", ans);
}

题目： 给出一个带边权的树形图，要求根节点到所有叶子节点的距离都相等。每次可以用 $1$ 的代价使任意一条边的边权加 $1$ 。问最小花费。

有一个关键点，假设某个节点向儿子的连边需要增加的长度为 $3, 5, 8$ ，实际上可以把 $3$ 塞到向父亲节点的连边中，这样花费就变少了。这就是核心的贪心思路。

那么第一次 $df s$ 把所有节点的深度都求出来。第二次找到所有子节点连边中最小需要增加的长度，然后把这个长度转移到父亲节点的连边并减去贡献。特判叶子节点。定义 $d p$ 数组为向父亲节点连边的长度。

ll depth[MAXN], mxdep;
ll dp[MAXN]; //i节点连向父亲的边的长度
ll ans = 0;
void dfs_pre(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        depth[to] = depth[now] + val;
        mxdep = max(mxdep, depth[to]);
        dfs_pre(to, now);
    }
}

void dfs(int now, int pre) {
    int cnt = 0; ll mn = INF;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        dfs(to, now);
        cnt++;
        mn = min(mn, dp[to]);
    }
    if (!cnt) {
        dp[now] = mxdep - depth[now];
        ans += dp[now];
        return;
    }
    if (now != rt) {
        dp[now] = mn;
        ans -= (cnt - 1) * mn;
    }
}

void solve() {
    n = read(), rt = read();
    for (int i = 1; i < n; i++) {
        int u, v; ll val;
        u = read(), v = read(), val = read();
        add(u, v, val);
        add(v, u, val);
    }
    dfs_pre(rt, -1);
    dfs(rt, -1);
    printf("%lldn", ans);
}

换根DP

有两种最长路径：

从当前节点往下，知道子树中某个节点的最长路径
从当前节点往上，再从其父节点出发且不回到该节点的最长路径

换根DP分两个步骤。一次dfs统计出当前子树内的节点对当前节点的贡献。再一次dfs遍历，统计出当前节点的父节点对当前节点的贡献。然后合并统计答案。

那么第一遍dfs预处理出儿子的最大贡献距离和次大贡献距离以及最大贡献儿子和次大贡献儿子的编号。因为如果当前节点是其父节点子树中最大路径上的点，则父节点子树的最大贡献不能算作对该节点的贡献，要取父节点的次大贡献。

$df s$ 注意顺序。第一次用子节点更新父亲（自下而上），所以先 $df s$ ；第二次用父亲更新儿子（自上而下），所以求完后再 $df s$ 。

int n;
int down1[MAXN], down2[MAXN], up[MAXN];
int son1[MAXN], son2[MAXN];

void dfs_down(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        dfs_down(to, now);
        if (down1[to] + val > down1[now]) {
            down2[now] = down1[now], son2[now] = son1[now];
            down1[now] = down1[to] + val, son1[now] = to;
        }
        else if (down1[to] + val > down2[now]) {
            down2[now] = down1[to] + val, son2[now] = to;
        }
    }
}

void dfs_up(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        int val = edge[i].val;
        if (to == pre) continue;
        if (son1[now] == to) {
            up[to] = val + max(up[now], down2[now]);
        }
        else {
            up[to] = val + max(up[now], down1[now]);
        }
        dfs_up(to, now); //最后再往下走
    }
}

void solve() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, max(down1[i], up[i]));
    printf("%dn", ans);
}

题目： 有一个带点权（奶牛数量）和边权（路径长度）的树。现要找一个点作为开会地点，使得奶牛走的路程最小。

可以随便选择一个点作为根节点往下 $df s$ 算出所有子节点到达这个选定根节点需要走的路程，然后进行换根 $D P$ 。定义 $d p [i]$ 表示 $i$ 这个节点作为根节点时奶牛走过的路程和。易得出这个方程由两个地方转移过来，儿子的子树和父亲上面的部分。

假设有一条边，此时已经算出了 $d p [n o w]$ ，若将 $t o$ 作为根节点，画图后可以发现包含 $t o$ 在内的子树深度全部减去当前边权的大小，其他节点的深度都增加了当前边权的大小。减少的大小为 $s i z [n o w] \times v a l$ ，增加的大小为 $(n - siz[now]) times val) $ 。因此可以用父节点来更新子节点的状态，典型的换根 $D P$ 。

ll a[MAXN];
ll siz[MAXN], dp[MAXN], depth[MAXN];
ll n, N;

void dfs_down(int now, int pre) {
    siz[now] = a[now];
    dp[now] = depth[now] * a[now];
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        depth[to] = depth[now] + val;
        dfs_down(to, now);
        siz[now] += siz[to];
        dp[now] += dp[to];
    }
}

void dfs_up(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        ll val = edge[i].val;
        if (to == pre) continue;
        dp[to] = dp[now] - siz[to] * val + (N - siz[to]) * val;
        dfs_up(to, now);
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        N += a[i];
    }
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        ll w = read();
        add(u, v, w);
        add(v, u, w);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        if (dp[i] < ans) {
            ans = dp[i];
        }
    }
    printf("%lldn", ans);
}

题目： 给出一颗 $n$ 个点的树，点带权，对于每个节点求出距离它不超过 $k$ 的所有节点权值和 $m_i$

$k \leq 20$

设 $d o w n [i] [j]$ 表示从 $i$ 点向下 $j$ 的范围内由多少牛， $d p [i] [j]$ 表示 $i$ 点的 $j$ 范围内有多少牛。

$d o w n [i] [j] = a [i] + \sum d o w n [so n] [j - 1]$ 。很好算，第一遍 $df s$ 求出来

然后画个图，发现 $d p [i] [j] = d p [f a] [j - 1] - d o w n [v] [j - 2] + d o w n [v] [j]$ 。又是要用父节点更新子节点，用换根 $D P$ 。

ll n, k;
ll a[MAXN];
ll dp[MAXN][25];
ll down[MAXN][25];

void dfs_down(int now, int pre) {
    for (int i = 0; i <= k; i++) down[now][i] = a[now];
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs_down(to, now);
        for (int j = 1; j <= k; j++)
            down[now][j] += down[to][j - 1];
    }
}

void dfs_up(int now, int pre) {
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dp[to][1] += down[now][0];
        for (int j = 2; j <= k; j++)
            dp[to][j] += dp[now][j - 1] - down[to][j - 2]; 
        //此时now以完成更新，用父亲来更新儿子 
        dfs_up(to, now);
    }
}

void solve() {
    n = read(), k = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) a[i] = read();
    dfs_down(1, -1);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = down[i][j];
    dfs_up(1, -1);
    for (int i = 1; i <= n; i++)
        printf("%lldn", dp[i][k]);
}

树上状态机

题目： 没有上司的舞会。状态1当前节点参加：儿子节点一定不参加；状态2当前节点不参加：儿子节点可参加可不参加

题目： 给定一棵包含 $n$ 个节点的树。需要在节点上放置一些哨兵，哨兵的视野范围是一条边，使得所有边都能被哨兵观察到。

这个状态机定义起来很简单。若当前节点放置哨兵，子节点可放可不放；若当前节点未放置哨兵，子节点必须放。定义 $d p [i] [1/0]$ ：以节点 $i$ 为根节点的子树，在 $i$ 上放置哨兵 $(1)$ 和不放哨兵 $(0)$ 的方案数量。

$d p [i] [0] = \sum d p [so n] [1] ， d p [i] [1] = \sum min (d p [so n] [1], d p [so n] [0])$

int dp[2][MAXN];
int n;

void init() {
    tot = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
    }
    memset(dp, 0x3f, sizeof dp);
}

void dfs(int now, int pre) {
    dp[0][now] = 0, dp[1][now] = 1;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs(to, now);
        dp[0][now] += dp[1][to];
        dp[1][now] += min(dp[0][to], dp[1][to]);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        int u, k;
        scanf("%d:(%d)", &u, &k);
        u++;
        while (k--) {
            int v = read();
            v++;
            add(u, v);
            add(v, u);
        }
    }
    dfs(1, -1);
    printf("%dn", min(dp[1][1], dp[0][1]));
}

题目： 现在改成观察所有的点，且放置卫兵有代价，使得代价最小。

这样有三种状态： $0$ 表示被父节点观察， $1$ 表示被自己观察， $2$ 表示被某个子节点观察

被父节点观察时，子节点要么被自己观察要么被其子节点观察

被自己观察时，子节点可以被父节点观察，可以被自己观察，也可以被其子节点观察

被子节点观察时，其中一个子节点必须被自己观察，其他子节点状态同 $0$ 。

其他都一样，就是多出来的这个状态最后找出代价最小的子节点，在 $d p [n o w] [0]$ 减去这个子节点的贡献，再加上 $d p [t o] [1]$ ，就是 $2$ 状态的花费代价。

int n;
ll a[MAXN];
ll dp[3][MAXN];
//0表示被父亲观察，1表示被自己观察，2表示被儿子观察
//0的话儿子要么被自己观察，要么被自己的儿子观察
//1的话儿子被自己，父亲，儿子观察
//2的话儿子被自己观察的状态中找一种最小的方案，其余的儿子和0同理

void dfs(int now, int pre) {
    dp[0][now] = 0, dp[1][now] = a[now], dp[2][now] = INF;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs(to, now);
        dp[0][now] += min(dp[1][to], dp[2][to]);
        dp[1][now] += min({dp[0][to], dp[1][to], dp[2][to]});
    }
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dp[2][now] = min(dp[2][now], dp[0][now] - min(dp[1][to], dp[2][to]) + dp[1][to]);
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) {
        int k, u;
        u = read(), a[u] = read(), k = read();
        while (k--) {
            int v = read();
            add(u, v);
            add(v, u);
        }
    }
    dfs(1, -1);
    printf("%lldn", min(dp[1][1], dp[2][1]));
}

数位DP模型

数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 $0 \to 9$ ，其他进制可类比十进制。

数位DP：用来解决一类特定问题，一般具有以下特征

要求统计满足一定条件的数的数量（集合属性为方案数）
条件经过转化后可以使用或者类比数位的思想去理解和判断
输入会提供一个区间范围作为统计的限制
上界很大，大到暴力会超时

题目要求一段区间内符合条件的数的个数，可以用前缀和思想转化为求两个前缀区间的问题。

$s u m [l, r] = s u m [1, r] - s u m [1, l - 1]$

统计答案可以选择记忆化搜索。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，在考虑每一位都可以填哪些数字，最后利用前缀和思想统计答案。

记忆化搜索中要引入的参数通常由：

当前枚举到的数位 $p os$
前几位搜索过的情况 $s t$ （视题目而定，如前一位是什么，前几位的总和，某个数出现了几次）
前几位的数字是否等于上界的前几位数字 $l imi t (0/1)$
是否有前导零 $l e a d (0/1)$

关于递归时的树型结构会在第一道例题中解释

使用记忆化搜索是为了优化当前搜索分支（废话），那么什么时候可以呢？就是在当前数位能够枚举集合内所有元素的时候（前面搜索的数没有紧密贴着上界），即 $! l imi t$

抄来的伪代码：

int dfs(int pos, int pre, int lead, int limit) {
    if (!pos) {
        边界条件
    }
    if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
    int res = 0, up = limit ? a[pos] : 无限制位;
    for (int i = 0; i <= up; i ++) {
        if (不合法条件) continue;
        res += dfs(pos - 1, 未定参数, lead && !i, limit && i == up);
    }
    return limit ? res : (lead ? res : dp[pos][sum] = res);
}
int cal(int x) {
    memset(dp, -1, sizeof dp);
    len = 0;
    while (x) a[++ len] = x % 进制, x /= 进制;
    return dfs(len, 未定参数, 1, 1);
}
int main() {
    cin >> l >> r;
    cout << cal(r) - cal(l - 1) << endl;
    return 0;
}

预处理基本参数：

$l e n ：$ 数位长度，一般根据这个来确定数组范围
$a_i：$ 每个数位的具体数字（上限）

$df s$ 函数：

if (!limit && !lead && ~dp[pos][pre]) return dp[pos][pre]; 只有无数位大小限制，无前导零的情况才算，不然都是未搜索完的情况
return limit ? res : dp[pos][pre] = res; 如果最后还有限制，返回 $res$ , 否则返回 $d p [p os] [res]$ 并记忆化

记忆化搜索基本参数：

$p os$ （必填），表示数字的位数（当前搜索的深度）。一般是选择 $a [1]$ 到 $a [n]$ 的顺序，边界条件为 $! p os$
$l imi t$ （必填），可以填数的限制。无限制的话从 $0 \to 9$ 随便填，否则只能填到 $a [i]$
$p re$ （选填），表示上一个数是多少
$l e a d$ （选填），前导零是否存在，1表示存在
$s u m$ （选填），搜索到当前数字所有数字之和
$c n t$ （选填），某个数字出现的次数

题目： 求给定区间 $[L, R]$ 满足：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。

本题较为特殊，对于该 $B$ 进制的数来说，每位要么填 $0$ 要么填 $1$ （互不相同），且填 $1$ 的个数恰好等于 $K$ 。 $s t$ 记录的就是前几位填过的 $1$ 的个数，本题不用考虑前导零。

定义状态为 解除限制后，前 $i$ 位 $1$ 出现过 $j$ 次时的方案数。此题中方案数对应数的个数

int l, r, k, b;
int a[MAXN], al;
int dp[MAXN][MAXN];

int dfs(int pos, int cnt, int limit) {
    //枚举完所有数，看1出现的次数是否等于k
    if (!pos) return cnt == k;
    //当前限制以解除，返回记忆化结果
    if (!limit && ~dp[pos][cnt]) return dp[pos][cnt];
    //这个状态还没出现过，往下搜
    int ans = 0;
    int up = limit ? a[pos] : 1;
    for (int i = 0; i <= up; i++) {
        if (cnt + i > k) continue;
        if (i > 1) continue;
        ans += dfs(pos - 1, cnt + i, limit && i == up);
    }
    return limit ? ans : dp[pos][cnt] = ans;
}

int calc(int x) {
    al = 0;
    memset(dp, -1, sizeof dp);
    while (x) {
        a[++al] = x % b;
        x /= b;
    }
    return dfs(al, 0, 1);
}

void solve() {
    l = read(), r = read(), k = read(), b = read();
    printf("%dn", calc(r) - calc(l - 1));
}

题目： 统计 $[L, R]$ 范围内 0123456789 出现的次数

需要判断前导零。并且注意一下和前导零相关的边界问题。若最后的数字是0，返回1；若还未解除前导零的限制且当前找的数是0，那么 $0$ 出现的次数应该不变始终为 $0$ 。

定义 $d p [i] [j]$ 为解除限制后前 $i$ 位 $k$ 这个数字（通过外层枚举来求得 $k$ ）出现了 $j$ 次的方案数。本题的方案数对应 $k$ 这个数字出现的次数。

int l, r;
int a[MAXN], al;
int dp[MAXN][MAXN]; //前i位num出现过j次的方案数

int dfs(int pos, int cnt, int num, int lead, int limit) {
    if (!pos) {
        if (!num && lead)
            return 1; //所有位上都是0
        else
            return cnt; //返回num出现过的次数
    }
    if (!limit && !lead && ~dp[pos][cnt]) return dp[pos][cnt];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        int nxt;
        if (i == num) {
            //如果i是要找的那个数
            if (!num) //要找的数是0，那么前导零的限制必须已解除
                nxt = cnt + !lead;
            else
                nxt = cnt + 1;
        }
        else
            nxt = cnt;
        ans += dfs(pos - 1, nxt, num, lead && !i, limit && i == up);
    }
    return limit ? ans : (lead ? ans : dp[pos][cnt] = ans);
}

int calc(int n, int x) {
    memset(dp, -1, sizeof dp);
    al = 0;
    while (n) {
        a[++al] = n % 10;
        n /= 10;
    }
    return dfs(al, 0, x, 1, 1);
}

void solve() {
    for (int i = 0; i <= 9; i++) {
        printf("%d ", calc(r, i) - calc(l - 1, i));
    }
    puts("");
}

int main() {
    while (scanf("%d%d", &l, &r), l || r) {
        if (l > r) swap(l, r);
        solve();
    }
    return 0;
}

题目： 找出给定 $[L, R]$ 区间内相邻数位之差大于 $2$ 的数字个数。

要考虑前导零。定义状态 $d p [i] [j]$ 为 解除限制后 第 $i$ 位数字为 $j$ 时的方案数，本题方案数对应合法数字的个数。

int l, r;
int a[MAXN], al;
int dp[MAXN][MAXN]; //第i位数为j时的方案数

int dfs(int pos, int pre, int lead, int limit) {
    if (!pos) {
        return 1;
    }
    if (!limit && !lead && ~dp[pos][pre]) return dp[pos][pre];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        if (abs(i - pre) < 2) continue;
        if (lead && !i)
            ans += dfs(pos - 1, -2, 1, limit && i == up);
        else
            ans += dfs(pos - 1, i, 0, limit && i == up);
    }
    return limit ? ans : (lead ? ans : dp[pos][pre] = ans);
}

int calc(int x) {
    memset(dp, -1, sizeof dp);
    al = 0;
    while (x) {
        a[++al] = x % 10;
        x /= 10;
    }
    return dfs(al, -2, 1, 1);
}

void solve() {
    l = read(), r = read();
    printf("%dn", calc(r) - calc(l - 1));
}

题目： 找出 $[L, R]$ 范围内从左到右数位非下降的数字的个数

不用考虑前导零，记录前驱就行。定义状态 $d p [i] [j]$ 为 解除限制后 第 $i$ 位数字为 $j$ 时的方案数，本题方案数对应数字的个数

int l, r;
int a[MAXN], al;
int dp[MAXN][MAXN];

int dfs(int pos, int pre, int limit) {
    if (!pos) {
        return 1;
    }
    if (!limit && ~dp[pos][pre]) return dp[pos][pre];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        if (i < pre) continue;
        ans += dfs(pos - 1, i, limit && i == up);
    }
    return limit ? ans : dp[pos][pre] = ans;
}

int calc(int x) {
    memset(dp, -1, sizeof dp);
    al = 0;
    while (x) {
        a[++al] = x % 10;
        x /= 10;
    }
    return dfs(al, -1, 1);
}

void solve() {
    printf("%dn", calc(r) - calc(l - 1));
}

int main() {
    while (scanf("%d%d", &l, &r) != EOF) {
        solve();
    }
    return 0;
}

题目： 给定 $[L, R]$ 区间内有多少数字的数位和是 $N$ 的倍数，（N由题目给出）。

不用考虑前导零，不用考虑前驱，记录一个 $s u m$ 表示数位和即可，边界条件是 !pos && sum % mod == 0

int l, r, mod;
int a[MAXN], al;
int dp[MAXN][105];

int dfs(int pos, int sum, int limit) {
    if (!pos) {
        if (sum % mod == 0) return 1;
        return 0;
    }
    if (!limit && ~dp[pos][sum]) return dp[pos][sum];
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos - 1, sum + i, limit && i == up);
    }
    return limit ? ans : dp[pos][sum] = ans;
}

int calc(int x) {
    al = 0;
    memset(dp, -1, sizeof dp);
    while (x) {
        a[++al] = x % 10;
        x /= 10;
    }
    return dfs(al, 0, 1);
}

void solve() {
    printf("%dn", calc(r) - calc(l - 1));
}

int main() {
    while (scanf("%d%d%d", &l, &r, &mod) != EOF) {
        solve();
    }
    return 0;
}

题意： 求 $1$ 到 $n$ 中每个数的二进制下的 $1$ 的个数的累乘。

不用考虑前导零，因为只关心 $1$ 的个数不关心排列方式。二进制拆分后得到长度 $l e n$ 作为搜索深度。定义 $d p [i] [j]$ 为前 $i$ 位出现了 $j$ 个 $1$ 时的方案数，本题方案数定义为 $1$ 的个数的累乘。由于求累乘，所有 $an s$ 一开始要赋为 $1$ ，另外边界的时候也要特判一下

ll dp[MAXN][MAXN];
ll r;
int a[MAXN], al;

ll dfs(int pos, int cnt, int limit) {
   if (!pos) {
       return max(1ll, (ll)cnt);
   }
   if (!limit && ~dp[pos][cnt]) return dp[pos][cnt];
   ll ans = 1;
   int up = limit ? a[pos] : 1;
   for (int i = 0; i <= up; i++) {
       int t = cnt;
       if (i) t++;
       ans = ans * dfs(pos - 1, t, limit && i == up) % mod;
   }
   return limit ? ans : dp[pos][cnt] = ans;
}

ll calc(ll x) {
   memset(dp, -1, sizeof dp);
   al = 0;
   while (x) {
       a[++al] = x % 2;
       x /= 2;
   }
   return dfs(al, 0, 1);
}

int main() {
   scanf("%lld", &r);
   printf("%lldn", calc(r));
   return 0;
}

单调队列优化DP模型

一般分为两种情况：

题目中给定一个区间范围 $k$ ，通过这个 $k$ 去思考
题目中为给出明确的，具体的，不可更改的范围，但是需要考虑到第 $i$ 位之前 $[i - k, i - 1]$ 区间的前缀和问题

题目： 求 $1 \leq l e n \leq k$ 的最大连续子序列和。

维护一个前缀和的单调队列。因为是前缀和，所以要预先插入一个 $0$ 来处理边界问题。

求最大前缀和，每次用当前的 $s u m [i]$ 减去 $s u m [q [hh]]$ 就是值，因为要最大所以队头要最小。

另外，长度大于等于1，也就是队头不能等于当前的 $i$ ，所以在先求最值再把当前的 $i$ 插入队尾。否则可能出现队头队尾相同的情况。

int n, k;
ll sum[MAXN], a[MAXN];
int q[MAXN];
int hh = 1, tt = 0;
void solve() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i]; 
    }
    ll ans = -INF;
    //枚举以i作为终点的，长度不超过k的最大子序和
    q[++tt] = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && i - q[hh] > k) hh++;
        ans = max(ans, sum[i] - sum[q[hh]]);
        while (hh <= tt && sum[q[tt]] >= sum[i]) tt--;
        q[++tt] = i;
        
    }
    printf("%lldn", ans);
}

单调队列实在是不会写，写一道意思意思。

概率期望DP模型

一般思路：由于起点往往只有 $1$ 个，终点有多个，因此需要倒着考虑。就像树形DP用子节点更新父节点那种思想，用记忆化搜索做。可以设 $d p [i]$ 表示从状态 $i$ 到状态 $n$ 的期望，那么 $d p [1]$ 即为总期望。

性质： $E (a x + b y) = a E (x) + b E (y)$

绿豆蛙的归宿： 给出一个有边权的 $D A G$ 图。如果有 $k$ 条离开某个点的道路，绿豆蛙可以选择任意一条道路离开该点，并且概率为 $1 k frac{1}{k}$ 。求从起点走到终点所经过的路径总长度期望。

ll n, m;
vector<pii> g[MAXN];
double dp[MAXN]; //以i作为起点，到达各个终点的路径期望之和

double dfs(int now) {
    if (dp[now] >= 0) {
        //已经搜索过了
        return dp[now];
    }
    int len = g[now].size();
    dp[now] = 0.0;
    for (int i = 0; i < len; i++) {
        int to = g[now][i].first;
        double val = g[now][i].second + 0.0;
        dp[now] += (val + dfs(to)) / (len + 0.0);
    }
    return dp[now];
}

void solve() {
    n = read(), m = read();
    memset(dp, ~0x3f, sizeof dp);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        u = read(), v = read(), w = read();
        g[u].pb(v, w);
    }
    dfs(1);
    printf("%.2lfn", dp[1]);
}

最后

以上就是斯文秀发为你收集整理的acm - 动态规划模板动态规划的全部内容，希望文章能够帮你解决acm - 动态规划模板动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：个人训练总结
浏览次数：71 次浏览
发布日期：2024-10-03 02:00:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_10_f0_13_z_26_x.html

acm - 动态规划模板动态规划

概述

动态规划

思维导图：

数字三角形模型

最长上升子序列模型

背包模型

01背包求最值

二维费用背包（就比01背包多开了一维）

01背包求方案数（记得初始化）

完全背包求最值（可以无限次选择）

多重背包（单调队列优化）

多重背包（二进制优化）

混合背包

一些变形

输出方案

分组背包+输出方案

01背包求最优方案数

有依赖的背包问题（树上背包）

有依赖的背包问题（体积和价值在边上）

有依赖的背包问题，根节点不止一个（森林）

有依赖的背包问题（分组背包）

状态机模型

状态压缩模型

棋盘类

集合类

区间DP模型

树形DP模型

换根DP

树上状态机

数位DP模型

单调队列优化DP模型

概率期望DP模型

最后

评论列表共有 0 条评论

发表评论取消回复

acm - 动态规划模板动态规划

概述

动态规划

思维导图：

数字三角形模型

最长上升子序列模型

背包模型

01背包求最值

二维费用背包（就比01背包多开了一维）

01背包求方案数（记得初始化）

完全背包求最值（可以无限次选择）

多重背包（单调队列优化）

多重背包（二进制优化）

混合背包

一些变形

输出方案

分组背包+输出方案

01背包求最优方案数

有依赖的背包问题（树上背包）

有依赖的背包问题（体积和价值在边上）

有依赖的背包问题，根节点不止一个（森林）

有依赖的背包问题（分组背包）

状态机模型

状态压缩模型

棋盘类

集合类

区间DP模型

树形DP模型

换根DP

树上状态机

数位DP模型

单调队列优化DP模型

概率期望DP模型

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复