动态规划做题笔记

February 26 2025

DP
- 线性DP
  - P1020 导弹拦截
- 区间DP
  - P1880 石子合并
  - P3146 248 G
  - P3147 262144P
  - UVA1630 串折叠 Folding 双倍经验: P4302 [SCOI2003]字符串折叠
  - P4170 涂色
  - P5851 Greedy Pie Eaters P
  - P1220 关路灯
  - P6879 スタンプラリー 3
  - P4766 Outer space invaders
  - 杂记
- 背包DP
  - P1941 飞扬的小鸟
  - P5020 货币系统
  - P1833 樱花(二进制优化)
  - P1064 金明的预算方案
  - P1417 烹调方案
  - 杂记
- 树形DP
  - 树形背包模板
  - 链式前向星模板
  - P2015 二叉苹果树
  - P2014 选课
  - P1270 "访问"美术馆
  - P1131 时态同步
  - P3047 Nearby Cows G
- 基环树
  - 基环树默认步骤
  - CF711D Directed Roads
  - P1453 城市环路
  - P2607 骑士
- 单调队列优化DP
  - 单调队列模板
  - P3572 PTA-Little Bird
  - CF1077F2 Pictures with Kittens (hard version)
  - P3089 Pogo-Cow S
- 概率DP
  - P1654 OSU!
  - CF148D Bag of mice
  - P3239 亚瑟王
- 混合DP
  - P4158 粉刷匠
- 状压DP
  - P1278 单词游戏
- 数位DP
  - 博客
  - 数位DP模板
  - P3413 萌数
  - P2235 Kathy函数
  - P4127 同类分布

DP

线性DP

P1020 导弹拦截

由题意可知题目要求的是最长不升子序列的长度以及不升子序列的最小个数. 由Dilworth定理可知偏序集上最小链划分中链的数量等于其反链长度的最大值, 也就是说, 要求不升子序列的最小个数等于最长上升子序列的长度. 所以这一题的问题转化为求一条最长不升子序列的长度以及一条最长上升子序列的长度.

O(n^2)的朴素算法即对每一个高度, 枚举在其前面的高度更高的点的值(某个点的值即以这个点的高度为结尾的子序列的最长长度), 答案即最大值+1, 不作过多赘述.

但是这题存在O(nlogn)的做法, 考虑用一个数组维护每个长度的不升子序列的末尾元素的最大值, 这样维护的原因是末尾元素的高度越高, 则能拼到这条子序列末尾的元素就更多.

那么, 对于每一个新的高度:

如果当前元素的高度小于等于加入该元素前最长不升子序列的末尾元素的最大值, 则在数组的末尾新增一项, 存储该元素的高度, 代表加入该元素后最长的不升子序列的末尾元素的高度, 也就是当前元素的高度;

否则, 用STL提供的二分查找在数组中找到第一个小于当前元素的高度的元素, 用当前元素的高度将其替换.

最后, 所求的最大长度即数组的大小.

为什么上述操作是合法的呢?

首先对于第一种可能性, 其合法性是显然的. 如果当前最长的子序列的末尾元素的高度比当前要插入的元素的高度更高, 说明这个元素是可以拼到当前最长的子序列的末尾从而形成一条新的长度为之前最长子序列长度+1的子序列的, 又因为这个长度的子序列第一次出现, 其末尾元素的最高高度自然是形成这条子序列的当前元素的高度.

对于第二种可能性, 有两个需要解释的点, 第一是为什么可以使用二分查找, 也即为什么我们维护的数组是单调不升的, 第二点是为什么是第一个小于当前元素的高度的元素而不是小于等于, 即使用upper_bound还是使用lower_bound.

第一点成立的原因是因为我们维护这个数组的方式确保了数组的单调不升性, 因为我们每次插入或修改元素时都确保该元素之前的元素的值均大于等于该元素的值, 因此数组一定是单调不升的.

对于第二点, 也是相对比较绕的点, 为什么一定是upper_bound而不能是lower_bound呢? 这是因为我们要确保最优, 则对于一个元素, 要找到末尾元素高度不小于待插入元素的序列中最长的序列, 插入这样的序列后形成的新序列 (注意这个序列不是我们找到的序列而是长度比我们找到的序列大1的序列, 也就是数组中下标+1的那一项) 的末尾元素的高度即待插入元素的高度. 这也就解释了为什么是upper_bound而不是lower_bound, 如果我们使用lower_bound, 那我们找到的是以不小于待插入元素的高度的元素为结尾的序列, 但这样的序列的数量不容易求得, 因此使用lower_bound + 1是错误的. 而如果我们使用的是upper_bound, 则确保了找到的那个序列一定比我们用lower_bound想要找到的序列中长度最长的那个序列的长度还要大1, 因此正确.

求最长上升子序列基本同理, 注意此时要确保最优, 则我们需要找到末尾元素高度比待插入元素小的序列中长度最大的序列并插入其末尾, 因此待插入序列末尾元素高度应大于等于待插入元素的高度, 即lower_bound.

代码:

#include <bits/stdc++.h>

#define debug() freopen("D:/Coding/Projects/Luogu/test.in", "r", stdin)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define endl '\n'

using namespace std;

__attribute__((unused)) typedef long long ll;
__attribute__((unused)) typedef unsigned long long ull;
__attribute__((unused)) const int maxN = 1e5 + 4, maxM = 1e6 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
int a[maxN] = {};

int main() {
    n = 0;
    vector<int> tail1, tail2;
    int tmp;
    while(cin >> tmp)
        a[++n] = tmp;

    for (int i = 1; i <= n; ++i) {
        if (tail1.empty() || a[i] <= *tail1.rbegin()) {
            tail1.push_back(a[i]);
        } else {
            int idx = upper_bound(tail1.begin(), tail1.end(), a[i], greater<int>()) - tail1.begin();
            tail1[idx] = a[i];
        }

        if (tail2.empty() || a[i] > *tail2.rbegin())
            tail2.push_back(a[i]);
        else {
            int idx = upper_bound(tail2.begin(), tail2.end(), a[i]) - tail2.begin();
            tail2[idx] = a[i];
        }
    }

    cout << tail1.size() << endl << tail2.size();
}

区间DP

P1880 石子合并

套板子判断min即可.

P3146 248 G

可以直接套板子并用dp[i][j]表示区间[i,j]可以合成的最大值, 这样做需要注意用一个bool数组标记这个区间的值是否直接合成的.

P3147 262144P

用dp[i][j]表示以j为左端点的能合成出i的区间右端点, 则可以得到状态转移方程为dp[i][j] = dp[i-1][dp[i-1][j]], 证明见图:

~~图弄丢了~~

UVA1630 串折叠 Folding 双倍经验: P4302 [SCOI2003]字符串折叠

难点在于判断是否可以折叠. 使用for (int i = 0; i < n; ++i) largerStr[i] == smallerStr[i % mod]判断, 同时需要注意判断长串是否为短串的整数倍后再折叠.

存储状态时可用结构体存储, 存储折叠串和折叠倍数并写一个函数解压缩即可.

剩余直接套区间DP的三层循环即可.

P4170 涂色

设dp[i][j]为子串[i,j]涂色所需次数, 则状态的转移有两种:

当子串的首尾相同时, 可视为第一次一次涂完首尾位置的颜色, 因此dp[i][j]=dp[i+1][j]=dp[i][j-1]\neq dp[i][j] + 1; 反之, 则将这个子串视为两个更小的子串, 则有dp[i][j] = \overset{j-1}{\underset{k=i}{min}}\{dp[i][j],dp[i][k]+dp[k+1][j] \}.

P5851 Greedy Pie Eaters P

设dp[i][j]为奶牛吃掉编号在[i,j]中的派可以获得的体重的最大值, cow[k][i][j]为满足i\leq l \leq r \leq j \wedge l \leq k \leq r 的牛的最大体重, 则可得dp[i][j]的转移方程为:

dp[i][j]=max\{\overset{j-1}{\underset{k=i+1}{max}}\{dp[i][k-1]+dp[k+1][j]+cow[k][i][j] \},dp[i+1][j]+cow[i][i][j],dp[i][j-1]+cow[j][i][j] \}

为便于遍历, 将奶牛吃掉两端的派的情况单独考虑.

再考虑奶牛不吃派的情况, 此时只需要按照传统的方式比较子区间的和与答案即可.

由于dp[i][j]在更新时限定了牛可以吃掉的派的范围一定在[i,j]内, 因此在状态转移方程中位于位置k的派一定是没有被吃掉的. 那么剩余需要求出的值是cow[k][i][j].

由于大区间覆盖小区间, 因此从小区间开始遍历, 对于每个区间的每个k, 均有cow[k][i][j]=max\{ cow[k][i+1][j],cow[k][i][j-1] \}, 即大区间的值只能由在其之内的比其小一个单位的区间更新, 那么这个状态只能由两种状态转移而来, 即cow[k][i+1][j],cow[k][i][j-1]. 如果用填表法的思路, 则对于同样遍历的遍历方式的每个k, 其状态都可以转移到两种状态, 即向左延伸一个单位或向右延伸一个单位.

两种方法的cow[k][i][j]更新方式代码如下:

for (int len = 1; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
        int r = l + len - 1;
        for (int k = l; k <= r; ++k) {
            cow[k][l - 1][r] = max(cow[k][l - 1][r], cow[k][l][r]);
            cow[k][l][r + 1] = max(cow[k][l][r + 1], cow[k][l][r]);
        }
    }
}

for (int len = 2; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
        int r = l + len - 1;
        for (int k = l; k <= r; ++k) {
            cow[k][l][r] = max(cow[k][l][r], max(cow[k][l + 1][r], cow[k][l][r - 1]));
        }
    }
}

P1220 关路灯

设计状态时, 由于老王走路每秒只能走1m, 因此采用dp[i][j] = max(dp[i+1][j], dp[i][j - 1])的状态. 设dp[i][j][0]为老王关完区间[i,j]内的灯后站在第i盏灯上浪费的最低功耗, dp[i][j][1]为老王关完区间[i,j]内的灯后站在第j盏灯上浪费的最低功耗.

由于状态的转移只有当老王向左或右移动1m时进行, 因此计算行走时浪费的功耗较为方便. 观察状态的转移, 对于dp[i][j][0], 老王有两种移动的方案: I. 从dp[i + 1][j][0]直接向左移动一格将其关闭; II. 从dp[i + 1][j][1]向左移动d_{j-i}格, dp[i][j][1]同理. 据此可以求出转移方程:

dp[i][j][0] = min\{dp[i][j][0],dp[i+1][j][0]+cost(i+1,i,i,j), dp[i+1][j][1]+cost(j,i,i,j) \}\\ dp[i][j][1] = min\{dp[i][j][1],dp[i][j-1][1]+cost(j,j-1,i-1,j-1),dp[i][j-1][0]+cost(j,i,i-1,j-1) \}

其中:

cost(i,j,l,r) = (p[i]-p[j])\times (prefix[l]+prefix[n]-prefix[r]) \\ prefix[i]=\overset{i}{\underset{j=1}{\sum}}w_i

P6879 スタンプラリー 3

这题与关路灯相对类似, 但增加了更多的难点. 首先是由于题目所给是一个环, 因此需要破环成链, 可以按照传统的开两倍数组空间的方法. 破环成链时, 为减少计算距离的麻烦, 可以在记录第二段的距离时加上L, 同时可以在数组的第n+1位置上插入一个虚构的x=L的起点以便初始化.

注意: 由于添加了一个虚构的起点, 因此遍历时区间长度的最大值应为n+1而非n!

剩下的状态转移方程与关路灯区别不大:

if (l < r && i && dp[l + 1][r][i - 1][0] + x[l + 1] - x[l] <= t[l])
    dp[l][r][i][0] = min(dp[l][r][i][0], dp[l + 1][r][i - 1][0] + x[l + 1] - x[l]);
dp[l][r][i][0] = min(dp[l][r][i][0], dp[l + 1][r][i][0] + x[l + 1] - x[l]);
if (l < r && i && dp[l + 1][r][i - 1][1] + x[r] - x[l] <= t[l])
    dp[l][r][i][0] = min(dp[l][r][i][0], dp[l + 1][r][i - 1][1] + x[r] - x[l]);
dp[l][r][i][0] = min(dp[l][r][i][0], dp[l + 1][r][i][1] + x[r] - x[l]);

if (l < r && i && dp[l][r - 1][i - 1][1] + x[r] - x[r - 1] <= t[r])
    dp[l][r][i][1] = min(dp[l][r][i][1], dp[l][r - 1][i - 1][1] + x[r] - x[r - 1]);
dp[l][r][i][1] = min(dp[l][r][i][1], dp[l][r - 1][i][1] + x[r] - x[r - 1]);
if (l < r && i && dp[l][r - 1][i - 1][0] + x[r] - x[l] <= t[r])
    dp[l][r][i][1] = min(dp[l][r][i][1], dp[l][r - 1][i - 1][0] + x[r] - x[l]);
dp[l][r][i][1] = min(dp[l][r][i][1], dp[l][r - 1][i][0] + x[r] - x[l]);

P4766 Outer space invaders

观察题意, 可以得到两个重要的结论:

解题时时间的长短是无关的, 因此可以对时间进行离散化从而减少空间的占用;

对每个时间段, 距离最远的外星人都应单独消灭.

因此, 设dp[i][j]为消灭所有满足i\leq a_i \leq b_i \leq j的外星人所需的最少燃料电池, 由结论2可以得出转移方程为

dp[i][j] = min\{ \overset{j-1}{\underset{mid=i+1}{min}}\{ dp[i][mid-1]+dp[mid + 1][j]+d_k \}, dp[i + 1][j]+d_i, dp[i][j - 1]+d_j \}

杂记

设计状态时应注意状态间的可复用性以及状态间的转移路径.
区间DP大致可分为两种形式的状态:
1. dp[i][j] = max(dp[i+1][j], dp[i][j - 1]);
2. dp[i][j]=\overset{j-1}{\underset{mid=i}{max}}\{dp[i][j], dp[i][mid] +dp[mid+1][j] \};
3. dp[i][j]=\overset{j-1}{\underset{mid=i}{max}}\{dp[i][j], dp[i][mid - 1] +dp[mid+1][j] + mid\}.

背包DP

P1941 飞扬的小鸟

用dp[i][j]表示当前在坐标(i, j)处所花费的最少屏幕点击数, 则状态转移方程为

dp[i][j] = \begin{cases} min(dp[i][j], dp[i-1][j + y[i-1]]) & j + y[i-1] \leq m \\ min(dp[i][j], \overset{\lfloor j/x[i-1]\rfloor}{\underset{k=1}{min}}\{dp[i - 1][j-k\times x[i-1]]\}+k ) & j-k\times x[i-1] > 0 \\ min(dp[i][j], \overset{m}{\underset{k=m-x[i-1]}{min}}\{dp[i][k]\}+1) & j=m \end{cases}

填表法应该会更好做.

P5020 货币系统

记忆化搜索即可.

P1833 樱花(二进制优化)

状态转移方程十分简单, 然而一般的多重背包的O(nTP)不足以通过此题, 通过二进制优化可以将时间复杂度降低至O(nTlog_2P)从而通过此题.

二进制优化的思想是将一个n重背包以二进制的形式表示, 如n=7时可分解为1,2,4, n=13时分解为1,2,4,6, 不难发现区间[1,n]中的任意一个数都可以通过二进制表示中的数的组合表示. 从而将n重背包转化成了有 \lceil log_2n \rceil个物品的0-1背包问题.

其代码如下:

int size = p[i], j = 1;	//size为当前物品个数
while (size > j) {
    size -= j;
    cost[i].push_back(j * a[i]);
    j <<= 1;
}
cost[i].push_back(j * a[i]);	//如果n + 1非2的整数次幂

P1064 金明的预算方案

注意题意中的 "每个主件可以有 0 个、1 个或 2 个附件。",因此转移方程可简单的表示为:

dp[j] = max(dp[j], dp[j - a[i].v] + a[i].v * a[i].p);
            if (a[i].aff.size() == 1 && j >= a[i].v + a[a[i].aff[0]].v) {
                dp[j] = max(dp[j], dp[j - (a[i].v + a[a[i].aff[0]].v)] + a[i].v * a[i].p + a[a[i].aff[0]].v * a[a[i].aff[0]].p);
                continue;
            }
            if (a[i].aff.size() < 2)
                continue;
            if (j >= a[i].v + a[a[i].aff[0]].v)
                dp[j] = max(dp[j], dp[j - (a[i].v + a[a[i].aff[0]].v)] + a[i].v * a[i].p + a[a[i].aff[0]].v * a[a[i].aff[0]].p);
            if (j >= a[i].v + a[a[i].aff[1]].v)
                dp[j] = max(dp[j], dp[j - (a[i].v + a[a[i].aff[1]].v)] + a[i].v * a[i].p + a[a[i].aff[1]].v * a[a[i].aff[1]].p);
            if (j >= a[i].v + a[a[i].aff[0]].v + a[a[i].aff[1]].v)
                dp[j] = max(dp[j], dp[j - (a[i].v + a[a[i].aff[0]].v + a[a[i].aff[1]].v)] + a[i].v * a[i].p + a[a[i].aff[0]].v * a[a[i].aff[0]].p + a[a[i].aff[1]].v * a[a[i].aff[1]].p);

读题读题读题!!!

P1417 烹调方案

由于美味指数与食材烹饪完成的时刻有关, 显然结果与食材的选择次序有关, 因此DP前应对数组进行排序. 设当前时刻为t, 其中两个相邻的食材属性分别为a_i,b_i,c_i和a_{i+1},b_{i+1},c_{i+1}, 可以求得:

先做第i个食材获得的美味指数为dp[t]+a_i-(t + c_i)\times b_i+a_{i+1}-(t+c_i+c_{i+1})\times b_{i+1};
先做第i+1个食材获得的美味指数为dp[t]+a_i-(t + c_i+c_{i+1})\times b_i+a_{i+1}-(t+c_{i+1})\times b_{i+1};

则先做第i个食材获得的收益为-c_i b_{i+1}+c_{i+1}b_i, 因此排序时比较函数的返回值应为-c_i\times b_{i+1}+c_{i+1}b_i > 0, 即c_{i+1}b_i >c_ib_{i+1}, 代码如下:

bool cmp(const s &a, const s &b) {
    return a.c * b.b < a.b * b.c;
}

剩下的问题为简单的0-1背包问题.

杂记

板子:

完全背包:

for (int i = 1; i <= n; ++i)
    for (int j = a[i].cost; j <= T; ++j)

0-1背包:

for (int i = 1; i <= n; ++i)
    for (int j = T; j >= a[i].cost; --j)

多重背包:

for (int i = 1; i <= n; ++i)
    for (int j = T; j >= a[i].cost; --j)
        for (int k = 1; j >= k * a[i].cost; ++k)

多重背包可以通过二进制优化转化为0-1背包问题.

树形DP

树形背包模板

void dfs(int u) {
    //不要使用dp[u]的值判断, 尤其是结果有可能取0的情况下!!!
    if (visited[u])
        return;
    //如果当前节点是叶子, 则特殊处理.
    if (a[u].son.empty())
        return;
    //先处理当前节点的所有子节点
    for (auto i : a[u].son)
        dfs(i);
    //枚举当前节点分配的容量
    for (int i = 1; i <= m; ++i) {
        //枚举子节点分配的容量
        for (int k = 0; k <= i; ++k) {
            //如果一个节点可能有超过2个节点, 则需另外进行分配, 可视作0-1背包处理.
            dp[u][i] = max(dp[u][i], dp[a[u].left][k] + dp[a[u].right][i - k]);
        }
    }
}

链式前向星模板

vector<int> nxt, head, to;

//建图, 建图前需对head数组进行初始化head.resize(n + 1, -1);
void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

/** 遍历子节点方式
for (int i = head[u]; ~i; i = nxt[i]) {
    int v = to[i];
}
 */

P2015 二叉苹果树

建图时需注意题目给出的边的信息不一定是从根到叶的顺序给出, 因此需用链式前向星进行建图, 建图时每条边需添加两次作为双向边. 同时建图时可以将边权下放至点权, 对每条边的权值都将其下放至离叶子较近处的节点.

然后看题不难发现这是一道树上背包问题, 设dp[i][j]为以i为根的子树保留j条树枝可以获得的最多的苹果, 则可以获得状态转移方程为dp[i][j] = \overset{j - 1}{\underset{k=0}{max}}\{ dp[i][j],dp[i.left][k]+dp[i.right][j-1-k] +value[i] \}.

上式中k的上界是j-1的原因是因为对于所有除了根节点以外的节点i, 为了到达这个节点都事先保留了一条通向i的边, 因此子节点可以保留的树枝要减一. 这也意味着需要特殊处理根节点, 可以将j的上界设为m+1.

代码如下:

const int maxN = 1e2 + 4, maxM = 1e4 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m;
int store[maxN][maxN] = {};
struct node {
    int value = 0;
    vector<int> son;
} a[maxN] = {};
ll dp[maxN][maxN] = {};

vector<int> nxt, head, to;
bool buildVisited[maxN] = {};
void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}
void build(int u, int value) {
    buildVisited[u] = true;
    a[u].value = value;
    for (int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if (buildVisited[v])
            continue;
        a[u].son.push_back(v);
        build(v, store[u][v] ? store[u][v] : store[v][u]);
    }
}

void dfs(int p) {
    dp[p][1] = a[p].value;
    if (a[p].son.empty())
        return;
    for (auto i : a[p].son)
        dfs(i);
    int sonN = a[p].son.size();
    for (int i = m; i > 1; --i) {
        if (sonN == 1) {
            dp[p][i] = max(dp[p][i], dp[a[p].son[0]][i - 1]);
            continue;
        }
        int left = a[p].son[0], right = a[p].son[1];
        dp[p][i] = max(dp[p][i], dp[left][i - (p != 1)] + a[p].value);
        dp[p][i] = max(dp[p][i], dp[right][i - (p != 1)] + a[p].value);
        for (int j = 1; j <= i - 1; ++j) {
            dp[p][i] = max(dp[p][i], dp[left][j] + dp[right][i - (p != 1) - j] + a[p].value);
        }
    }
}

int main() {
    n = read(), m = read();
    head.resize(n + 1, -1);

    for (int i = 1; i <= n - 1; ++i) {
        int u = read(), v = read(), s = read();
        store[u][v] = s;
        add(u, v);
        add(v, u);
    }
    build(1, 0);
    dfs(1);
    cout << dp[1][m];
}

P2014 选课

同样是一道树形背包问题, 与二叉苹果树的主要区别是这道题目里的树是多叉树.

观察题意, 题目给出的是一个森林, 森林里的每棵树都以一门没有先修课的课为根, 注意到如果把这些课的先修课设为编号为0的不存在的课则可以将森林转化为一棵以编号为0的课为根的树, 将根节点的学分设为0. 由于这样处理添加了一门不存在的课一定会被"选", 因此容量的上界应设为m+1.

则按照多叉树的树形背包的解决方法解决问题即可, 下面的代码使用了多重背包来解决各子节点的分配问题:

__attribute__((unused)) const int maxN = 3e2 + 4, maxM = 3e4 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m;
ll dp[maxN][maxN] = {};
int dp2[maxN] = {};
struct node {
    int value = 0;
    vector<int> son;
} a[maxN] = {};

void dfs(int p) {
    int sonN = a[p].son.size();
    dp[p][1] = a[p].value;
    
    if (!sonN) {
        return;
    }
    for (auto i: a[p].son)
        dfs(i);

    //多重背包, 设dp2[i]为当前节点使用了容量i可以获得的最大学分.
    memset(dp2, 0, sizeof dp2);
    for (int j = 0; j < sonN; ++j) {
        auto son = a[p].son[j];
        for (int i = m + 1 - (p != 0); i >= 1; --i) {
            for (int k = 1; i - k >= 0; ++k) {
                dp2[i] = max(dp2[i], dp2[i - k] + dp[son][k]);
            }
        }
    }

    for (int i = 2; i <= m; ++i) {
        dp[p][i] = a[p].value + dp2[i - 1];
    }

    if (!p)
        dp[p][m + 1] = dp2[m];
}

int main() {
//    debug();
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        int u = read(), value = read();
        a[u].son.push_back(i);
        a[i].value = value;
    }

    dfs(0);
    cout << dp[0][m + 1];
}

P1270 "访问"美术馆

注意到题目的数据是以DFS序给出的, 因此建图时需注意.

题目中小偷偷一副画需要5分钟, 同时小偷偷完东西需要返回, 因此进入一个房间并偷画的花费是a[i].len + 5 * a[i].value, 剩下的解决方法则是普通的树上0-1背包(我也不知道为什么可以直接视为0-1背包处理, 难道进入一个房间必须偷完画吗? 同时题解一致提及了小偷的可用时间应该小于警察的到达时间, 但是我的代码没有提到这一点也通过了题目), 代码如下:

更新: 在考虑一个房间里的画不拿完的情况下的确需要输出dp[1][m-1]才能AC了(

改动附于代码中

__attribute__((unused)) const int maxN = 1e2 + 4, maxM = 6e2 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int m;
struct node {
    int len = 0;
    int value = 0;
    int left = 0;
    int right = 0;

    node(int le = 0, int v = 0, int l = 0, int r = 0) : len(le), value(v), left(l), right(r) {}
};

int size = 0;
node a[maxN] = {};
int dp[maxN][maxM] = {};

void build(int t, int v) {
    int now = ++size;
    a[now].len = t;
    a[now].value = v;
    if (v)
        return;
    int tt = read(), vv = read();
    a[now].left = size + 1;
    build(tt, vv);
    tt = read(), vv = read();
    a[now].right = size + 1;
    build(tt, vv);
}

void dfs(int p) {
    const node &now = a[p];
    if (!now.left) {
        dp[p][2 * now.len + 5 * now.value] = now.value;
        return;
    }
    /** 正确代码
    if (!now.left) {
        for (int i = 1; i <= now.value; ++i) {
            for (int j = 2 * now.len + i * 5; j < min(m + 1, 2 * now.len + 5 * (i + 1)); ++j) {
                dp[p][j] = i;
            }
        }
        return;
    }
    */
    dfs(now.left);
    dfs(now.right);
    for (int i = m; i >= 2 * now.len; --i) {
        for (int j = 0; j <= i - 2 * now.len; ++j) {
            dp[p][i] = max(dp[p][i], dp[now.left][j] + dp[now.right][i - 2 * now.len - j]);
        }
    }
}

int main() {
    m = read();
    int t0 = read(), v0 = read();
    build(t0, v0);
    dfs(1);
    cout << dp[1][m];
    /** 正确代码
    cout << dp[1][m - 1];
    */
}

P1131 时态同步

题面梆臭, 简单来说就是一棵多叉树, 给点边权, 你所需要做的就是让根节点到所有叶子节点的距离都相等. 因此这是一道较简单的树形DP, 设一个节点的某条出边的权值为w_i, 这条出边对应的子节点的出边的权值为son_i.w(由于递归处理, 因此子节点的出边一定已经处理完毕, 直到叶子节点没有出边, 则处理叶子节点的父节点时对应的son_i.w=0) , 则首先预处理所有节点的所有w_i + son_i.w的最大值, 而后对每个节点的出边所需的道具数求和即可, 代码如下:

__attribute__((unused)) const int maxN = 5e5 + 4, maxM = 6e2 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m;
struct node {
    int self = 0, sonMax = 0;
    ll sonSum = 0;
    vector<int> son;
} a[maxN] = {};

vector<int> nxt, head, to, weight;
void add(int u, int v, int w) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
    weight.push_back(w);
}

vector<bool> buildVisited;
void build(int u, int w) {
    buildVisited[u] = true;
    a[u].self = w;
    for (int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if (buildVisited[v])
            continue;
        build(v, weight[i]);
        a[u].son.push_back(v);
        a[u].sonMax = max(a[u].sonMax, a[v].sonMax + a[v].self);
        a[u].sonSum += a[v].self;
    }
}

ll calc(int u) {
    ll ans = 0;
    for (auto i : a[u].son) {
        ans += calc(i);
        ans += a[u].sonMax - (a[i].sonMax + a[i].self);
    }

    return ans;
}

int main() {
//    debug();
    n = read(), m = read();
    buildVisited.resize(n + 1);
    head.resize((n + 1) << 1, -1);

    for (int i = 1; i <= n - 1; ++i) {
        int u = read(), v = read(), t = read();
        add(u, v, t);
        add(v, u, t);
    }
    build(m, 0);
    cout << calc(m);
    return 0;
}

P3047 Nearby Cows G

观察题意, 可以发现题目所给出的树没有指定根节点, 不妨指定编号为1的节点为根.

题目要求的是与一个节点相距小于等于k的节点的和, 因此观察指定根后的这棵树的某个节点, 与其相距k的节点可以分为两类, 第一类包括这个节点自身以及位于这个节点的子树的符合要求的点, 第二类则是这个节点的父亲之上的符合要求的节点.

第一类节点相对好求, 不妨设dp[i][j][0]为与节点i相距小于等于j的位于节点i的子树的所有节点的和(包括节点i本身), 则可以得到其转移方程为dp[i][j][0] = (\sum dp[i.son][j-1][0])+c_i;

第二类节点则相对更难一些, 设需要求的第二类的节点的和为dp[i][j][1], 则对节点i的每个祖先, 将节点i的祖先以及位于这个祖先的子树中的相距对应距离的节点求和, 再减去重复计算的部分即可得到转移方程(这个过程也是递归的): dp[i][j][1] = dp[i.father][j - 1][1]+dp[i.father][j-1][0]-dp[i][j-2][0].

式子中第一部分是递归向上求一个节点的所有祖先, 第二部分则是对节点i求得其父亲的子树中符合要求的节点之和, 第三部分则是去重, 去掉节点i的父亲的子树中节点i及其子树被重复计算的部分.

由于第二类节点的求法涉及到了递归, 则需要处理递归边界的问题(第一类节点也是递归求得的, 其边界即叶子节点).

首先当j=1时, 状态转移方程的第三部分超越了边界, 因此需特殊处理, 不难得到j=1时所求的值即当前节点的父亲的值, 因此当j=1时, dp[i][j][1] = c_{i.father};

同时由于我们指定了这棵树的根为1, 因此当i=1时, 由于1不再有父亲, 因此dp[i][j][1]=0(dp[i][j][1]处理的是一个节点的父亲节点部分, 由于根节点没有父亲, 因此直接置0).

通过以上两步, 问题就解决了, 对每个节点i所求的答案等于dp[i][j][0] + dp[i][j][1].

坑点:记忆化搜索时判断一个点是否已经求得不要使用dp[i][j][direction]的值是否为零来判断!! 一个点的取值可能为0!!!

基环树

基环树默认步骤

通过并查集判环, 具体步骤为: 建图时将边的两个端点在并查集中查询祖先, 若一条边的两个端点都已经存在于某个联通块中, 则这条边是对应联通块中构成环的那条边.

若一条边是构成环的那条边(多余那条边), 可将其标记并保存下来, 这条边可不插入到图中以便搜索; 反之, 则正常将这条边插入到图中, 同时将这条边的两个端点合并到集合中.

此时可根据问题选择不同的解决方式: 其中一种方法是将环上的点的子树的信息合并到点上, 再对环进行处理; 又或者断开第二步得到的边, 对两个端点单独处理.

CF711D Directed Roads

这一题对应上述第一类解决方法, 由题意可得这是一个n点n边的图, 由于一颗树是一个n点n-1边的图, 因此不难发现题目所给的图是一个基环树. 需要注意的是, 由基环树组成的森林具有同样的点数和边数, 因此在做题时需要注意图中可能有多个联通块需要处理, 本题就是这种情况.

而对于这道题, 题目需要求的是给每条边指定方向使得图不构成环的方案数. 由于要构成环, 只有当原先的环上的边方向均相同时才能满足环的要求, 而不在环上的边的方向不影响环的构成, 因此对其中一颗基环树的方案数为(2^{N_i-len_i}\times2^{len_i}-2)(设树的大小为N, 环的大小为len), 则对整个基环树森林, 其方案数为:

2^{N_1-len_1}(2^{len_1}-2)\times\dots\times2^{N_x-len_x}(2^{len_x}-2)=2^{N-\sum{len_i}}\times\prod{2^{len_i}-2}

因此, 预处理出每条构成环的边的起点与终点后, 通过DFS从起点到终点将路径上的边标标记为环上的边并计算环上的边的数量, 而后通过上式求出答案即可.

代码:

const int maxN = 2e5 + 4, maxM = 1e5 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
int father[maxN] = {}, rnk[maxN] = {}, out[maxN] = {};

ull FastPower(ll base, ll power) {
    ull ans = 1;
    while (power) {
        if (power & 1)
            ans = (ans * base) % MOD;
        power >>= 1;
        base = (base * base) % MOD;
    }
    return ans % MOD;
}

//用于找成环边的并查集的初始化.
void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        rnk[i] = 1;
    }
}

//并查集查询公共祖先
int find(int x) {
    return x == father[x] ? x : find(father[x]);
}

//并查集合并操作
void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (rnk[x] <= rnk[y])
        father[x] = y;
    else
        father[y] = x;
    if (rnk[x] == rnk[y] && x != y)
        ++rnk[y];
}

//链式前向星
vector<int> nxt, head, to;

void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

vector<pair<int, int>> ring;

bool visited1[maxN] = {};

ull dfs1(int u, int start) {
    visited1[u] = true;
    ull ans = 0;
    for (int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if (v == start)
            return 1;
        if (visited1[v])
            continue;
        ull tmp = dfs1(v, start);
        ans = (ans + tmp) % MOD;
    }
    return ans ? (ans + 1) % MOD : (ans) % MOD;
}

int main() {
//    debug();
    n = read();
    init();
    head.resize(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        out[i] = read();
        if (find(i) == find(out[i])) {
            ring.emplace_back(i, out[i]);
            continue;
        }
        merge(i, out[i]);
        add(i, out[i]);
        add(out[i], i);
    }

    ull ans, sum = 0, tmp = 1;
    for (auto i : ring) {
        ull tmp2 = (dfs1(i.first, i.second) + 1) % MOD;
        sum = (sum + tmp2) % MOD;
        tmp = (tmp * (FastPower(2, tmp2) - 2) % MOD) % MOD;
    }
    ans = (FastPower(2, n - sum) * tmp) % MOD;
    cout << ans % MOD;
}

P1453 城市环路

这一题对应了上面提到的第二类解决方法, 由于开的店两两之间不能相邻, 因此可以处理出构成环的最后一条边后将其断开, 对断开边之后得到的树的三种情况求出答案, 即断开边的两个端点选其中之一或两个端点均不选.

设断开的边的左端点为l, 右端点为r, 求解时, 对只选左端点的情况, 可以以l为根, 强制不选择r做一次最大子树和问题. 对其余两种情况, 则可以以r为根做一次最大子树和问题. 强制不选择某个点, 可以将该点的权值设为-\infty.

注: 将点权设为-\infty后需将其设置回原值.

代码:

__attribute__((unused)) const int maxN = 1e5 + 4, maxM = 1e5 + 4, maxA = 14, maxB = 34, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
double k;
int p[maxN] = {};
int father[maxN] = {}, Rank[maxN] = {};

void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        Rank[i] = 1;
    }
}

int find(int x) {
    return x == father[x] ? x : find(father[x]);
}

void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (Rank[x] <= Rank[y]) {
        father[x] = y;
    } else
        father[y] = x;
    if (Rank[x] == Rank[y] && x != y) {
        ++Rank[y];
    }
}

vector<int> nxt, head, to;

void add(int u, int v) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

int x, y;
bool visited[maxN] = {};
int dp[2][maxN] = {};
bool checked[2][maxN] = {};

int dfs(bool isChosen, int u, int fa, int ign) {
    if (checked[isChosen][u])
        return dp[isChosen][u];

    int tmp = p[ign];
    if (fa == -1) {
        p[ign] = -INF;
    }
    checked[isChosen][u] = true;
    int ans = isChosen ? p[u] : 0;
    for (int i = head[u]; ~i; i = nxt[i]) {
        int v = to[i];
        if (v == fa)
            continue;
        if (isChosen) {
            ans += dfs(false, v, u, ign);
        } else {
            ans += max(dfs(true, v, u, ign), dfs(false, v, u, ign));
        }
    }

    if (fa == -1) {
        p[ign] = tmp;
    }
    return dp[isChosen][u] = ans;
}

int main() {
//    debug();
    n = read();
    head.resize(n + 1, -1);
    init();
    for (int i = 0; i < n; ++i)
        p[i] = read();
    for (int i = 1; i <= n; ++i) {
        int u = read(), v = read();
        if (find(u) == find(v)) {
            x = u;
            y = v;
            continue;
        }
        merge(u, v);
        add(u, v);
        add(v, u);
    }
    cin >> k;
    if (n == 1) {
        printf("%.1f", 1.0 * p[0] * k);
        return 0;
    }

    int ans = max(dfs(true, x, -1, y), dfs(false, x, -1, y));
    memset(dp, 0, sizeof dp);
    memset(checked, 0, sizeof checked);
    ans = max(ans, dfs(true, y, -1, x));

    printf("%.1f", 1.0 * ans * k);

    return 0;
}

P2607 骑士

与上题思路类似, 只是需要注意的是这一题的图不一定只有一个联通块.

单调队列优化DP

单调队列模板

使用场景: 若题目的状态转移方程符合dp[i] = \overset{i+x}{\underset{j=i-x}{max}}\{ dp[j] \} + constant的形式, 则可以使用单调队列进行优化. 注意区间需要连续. 使用时插入最右的边界, 检查左边界是否合法.

需注意左右边界是否搞反, 是否有非法的状态被插入等!

for (int i = 2; i <= n; ++i) {
    int l = 1, r = 0;
    //将区间[1, t]内插入.
    for (int j = 1; j <= min(m, t); ++j) {
        while (l <= r && dp[i - 1][j] >= dp[i - 1][q[r]])
            --r;
        q[++r] = j;
    }
    for (int j = 1; j <= m; ++j) {
        //检查左边界.
        while (l <= r && q[l] < j - t)
            ++l;
        //防止插入非法状态.
        if (j + t <= m) {
            while (l <= r && dp[i - 1][j + t] >= dp[i - 1][q[r]])
                 --r;
            //插入最右的值
            q[++r] = j + t;
        }
        //访问. 左边界检查步骤的位置在访问前即可. 右边界的检查需在插入前进行, 插入和访问的相对位置取决于被插入的状态是否需要被访问自由决定.
        dp[i][j] = dp[i - 1][q[l]] + a[i][j];
    }
}

P3572 PTA-Little Bird

用dp[i]表示到达第i棵树的最小劳累值, 维护区间[i-k,i-1]的单调队列, 比较时劳累值更小的在前, 若劳累值相等则高度更高的在前即可.

CF1077F2 Pictures with Kittens (hard version)

如果m<\frac{n}{k}则不可能满足条件, 输出-1.

令dp[i][j]表示选了j个数且第j个数为数列中第i个数时和的最大值, 对每个j维护一个区间为[i-k,i-1]的单调队列, 取最大值即可.

P3089 Pogo-Cow S

一道明显的单调队列优化DP题目, 但是由于题目中目标点的位置x_i的范围为[0,10^6], 显然不可能枚举坐标轴上的每一个点, 而是枚举每个目标点的位置, 这导致了这一题单调队列的维护与上面的题较为不同.

对于上面的题, 对队列的每次访问, 最后都只需要向队列内插入一次值, 然而这里由于我们枚举的是目标点的位置, 因此每次访问前都需将所有合法的状态都插入到队列中. 核心代码如下:

//dp[i][j]表示当前在第i个目标点, 上一个目标点为第j个目标点能得到的最大得分.
for (int j = 1; j <= n; ++j) {
    dp[j][j] = s[j].val;
    ans = max(ans, dp[j][j]);
    for (int i = j + 1, cur = j; i <= n; ++i) {
        dp[i][j] = dp[i - 1][j] - s[i - 1].val;
        while (cur >= 1 && abs(s[j].pos - s[cur].pos) <= abs(s[i].pos - s[j].pos)) {
            dp[i][j] = max(dp[i][j], dp[j][cur]);
            --cur;
        }
        dp[i][j] += s[i].val;
        ans = max(ans, dp[i][j]);
    }
}

概率DP

P1654 OSU!

题目要求得分的期望, 则设dp[i], 表示的是第i位为1时得分的期望,

那么由(x+1)^3=x^3+3x^2+3x+1可知在连续的1串后面添加一个1的贡献为3x^2+3x+1,

则从dp[i-1]求得dp[i]的式子可表示为dp[i+1]=p[i] \times (dp[i-1]+3x^2+3x+1)+(1-p[i])*dp[i-1],

那么再令dp_1[i-1]表示上式中的, dp_2[i-1]表示上式中的x^2并维护即可.

由于式子中的x^2与x都是在连续的1的条件下出现的, 则可知dp_1[i]与dp_2[i]的含义均为连续的1串中第i位是1的得分期望(不需要考虑1-p[i]的情况), 因此由(x+1)=x+1和(x+1)^2=x^2+2x+1可得他们的状态转移方程为

dp_1[i] = (dp_1[i - 1] + 1) \times p[i]

dp_2[i] = (dp_2[i-1]+2dp_1[i-1]+1) \times p[i]

那么此时代码就呼之欲出了.

CF148D Bag of mice

题目要求公主赢的概率, 则设dp[i][j], 表示的是当前背包剩余i只白鼠, j只黑鼠时公主赢的概率.

只考虑公主获胜的概率, 则有下列转移:

公主抓到白鼠, 获胜概率为\frac{i}{i + j};
公主抓到黑鼠, 且黑龙抓到一只黑鼠并逃走一只黑鼠, 获胜概率为\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2} \times dp[i][j-3], 此时需保证j \geq3;
公主抓到黑鼠, 且黑龙抓到一只黑鼠并逃走一只白鼠, 获胜概率为\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2} \times dp[i - 1][j - 2],此时需保证i \geq 1 \wedge j \geq 2.

同时边界条件为:

i = 0时dp[i][j] = 0;
i > 0 \wedge j=0时dp[i][j] = 1.

据此可以写出代码:

dp[i][j] += 1.0 * i / (i + j);
	if (i >= 1 && j >= 2)
		dp[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * dp[i - 1][j - 2];
	if (j >= 3)
		dp[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * dp[i][j - 3];

顺序遍历即可.

P3239 亚瑟王

由于各卡牌获得的收益彼此独立, 因此设第i张卡牌最终触发的期望为E_i, 则题目所求的ans = \overset{n}{\underset{i=1}{\sum}}E_i\times d_i, 则问题转化为求出每张卡牌最终触发的期望.

如果设dp[i][j]为经过r轮游戏后前i张牌共发动了j张的期望, 则期望E_i可由式子E_i = dp[i-1][j]\times (1-(1-p[i])^{r-j})求得, 则此时问题转化为求出dp[i][j]的值.

注意到dp[i][j]可以由两种情况转化而来, 即第i张卡牌发动和第i张卡牌不发动两种情况. 第一种情况求得的dp_1[i][j]=dp[i - 1][j - 1] \times (1 - (1-p_i)^{r - (j - 1)}), 第二种情况求得的dp_2[i][j] = dp[i - 1][j] * (1-p_i)^{r - j}, 因此dp[i][j]=dp_1[i][j]+dp_2[i][j](若两种情况分别成立). 此时我们可以得到所需代码.

为优化常数, 可以先预处理1-p_i的幂, 令Pow[i][j] = (1-p_i)^j, 代码如下:

for (int i = 1; i <= n; ++i) {
    Pow[i][0] = 1;
    long double calc = (1 - p[i]);
    for (int j = 1; j <= r; ++j) {
        Pow[i][j] = Pow[i][j - 1] * calc;
    }
}

dp部分:

dp[1][0] = Pow[1][r], dp[1][1] = 1 - dp[1][0];
	for (int i = 2; i <= n; ++i) {
        //游戏最多进行r轮, 因此j的上界应为i和r中较小的那个
		for (int j = 0; j <= min(i, r); ++j) {
            //第一种情况发生, 即第i张卡牌发动时j一定大于0
            if (j)
                dp[i][j] += dp[i - 1][j - 1] * (1.0 - Pow[i][r - (j - 1)]);
            //第二种情况发生, 即第i张卡牌不发动时i一定小于j
            if (i < j)
                dp[i][j] += dp[i - 1][j] * Pow[i][r - j];
        }
    }

完整代码:

const int maxN = 3e2 + 4, maxR = 2e2 + 4, MOD = 1e9 + 7, INF = 0x3f3f3f3f, Mod = 10000;
int n, r;
long double p[maxN] = {};
int d[maxN] = {};
long double Pow[maxN][maxR] = {};
long double dp[maxN][maxR] = {};

void init() {
    memset(p, 0, sizeof p);
    memset(d, 0, sizeof d);
    for (auto & i : Pow) {
        memset(i, 0, sizeof i);
    }
    for (auto & i : dp) {
        memset(i, 0, sizeof i);
    }
    cin >> n >> r;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> d[i];
    }
    for (int i = 1; i <= n; ++i) {
        Pow[i][0] = 1;
        long double calc = (1 - p[i]);
        for (int j = 1; j <= r; ++j) {
            Pow[i][j] = Pow[i][j - 1] * calc;
        }
    }
}

int main() {
//    debug();
    int T;
    cin >> T;
    while (T--) {
        init();
        dp[1][0] = Pow[1][r], dp[1][1] = 1 - dp[1][0];
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= min(i, r); ++j) {
                if (j)
                    dp[i][j] += dp[i - 1][j - 1] * (1.0 - Pow[i][r - (j - 1)]);
                if (i < j)
                    dp[i][j] += dp[i - 1][j] * Pow[i][r - j];
            }
        }
        long double ans = dp[1][1] * d[1];
        for (int i = 2; i <= n; ++i) {
            long double probability = 0;
            for (int j = 0; j <= min(i - 1, r); ++j) {
                probability += dp[i - 1][j] * (1.0 - Pow[i][r - j]);
            }
            ans += probability * d[i];
        }
        cout << fixed << setprecision(10) << ans << '\n';
    }
}

注意事项:

对每一个样例都应将所有数组进行初始化.

保留到小数点后10位.

每个样例的输出后记得换行.

混合DP

P4158 粉刷匠

可以看出, 问题对于每一行是区间DP, 对于整体而言是以每行为元素的背包DP.

则对于每一行而言:

令dp_2[i][j][k]表示第i行区间[1,j]粉刷了k次能得到的最大值, 则其状态转移方程为

dp_2[i][j][k] = \overset{j-1}{\underset{l = 0}{\max}}\{dp_2[i][j-l][k-1]+max\{\sum_{j-l+1}^{j}{蓝色格子},\sum_{j-l+1}^{j}{红色格子}\}\}

蓝色格子和红色格子的总和的比较可通过处理区间内蓝色格子数量的前缀和可较为方便的得出.

状压DP

P1278 单词游戏

字符串最多有16个, 其是否被选取的状态对应i中二进制位的0和1.

设dp[i][j]为当前状态为i, 最后被选取的字符串为第j个时游戏的最大复杂度.

则遍历状态i:1\rightarrow 2^n-1, 遍历状态i最后被选取的字符串j:0\rightarrow n - 1(需判断i中是否包含j), 最后遍历可选状态k:0\rightarrow n-1(需判断状态k不被i包含), 并通过状态转移方程dp[i+2^k][k] = max\{ dp[i+2^k][k], dp[i][j] + \lvert S_k \rvert \}更新即可.

PS:需注意下标问题, 将字符串从下标0开始存储的话, 则对应状态应为1 << k

数位DP

博客

知乎上一篇讲得很好的博客.

数位DP模板

ll n, m;
int len, a[maxN] = {};
ll dp[10][10][2] = {};

//pos表示当前遍历到哪一位(pos对应数字位数从大到小, 因此后面res的值为a[pos - len + 1]), pre保存上一位的值, state保存前面几位是否满足条件
//limit表示前面几位是否均达到上界, lead表示前面几位是否均是前导零
ll dfs(int pos, int pre, bool state, bool lead, bool limit) {
    //遍历完所有位, 如果满足条件则返回
    if (pos > len)
        return state;
    //如果已经求过则直接返回
    if (dp[pos][pre][state] != -1 && !lead && !limit)
        return dp[pos][pre][state];
    ll ans = 0;
    //如果之前几位都达到上界, 则当前位同样不能超过上界
    int res = limit ? a[len - pos + 1] : 9;
    //遍历这一位可能的取值
    for (int i = 0; i <= res; ++i) {
        //如果之前几位都达到上界且当且位也达到上界, 则下一位的limit的值也为true
        bool li = (limit && (i == res));
        //如果之前几位都是0且这一位也是0, 则下一位的lead的值也为true
        bool st = 满足条件;
        if (lead && !i)
            ans += dfs(pos + 1, 0, st, true, li);
        else {
            ans += dfs(pos + 1, i, st, false, li);
        }
    }
    //状态具有可复用性则保存
    if (!lead && !limit)
        dp[pos][pre][state] = ans;
    return ans;
}

ll solve(ll num) {
    len = 0;
    //获取数字各位的值, 从下标1开始保存数字从小到大各位的值
    while (num) {
        a[++len] = num % 10;
        num /= 10;
    }
    memset(dp, -1, sizeof dp);
    return dfs(1, 0, false, true);
}

int main() {
//    debug();
    n = read(), m = read();
    while (n || m) {
        cout << (m - n + 1) - (n ? solve(m) - solve(n - 1) : solve(m) - solve(n)) << endl;
        n = read(), m = read();
    }
}