DP笔记 2021.2.4 下午

\(w_{x, y}\) 为第 \(x\) 到第 \(y\) 个格子的最多同色格子数, 哪个颜色出现的多刷哪个, 直接记一个前缀和即可.

有多条木板, 设 \(f_{i, j}\) 表示前 \(i\) 个木板刷 \(j\) 次的最大答案.

其实像这种般的 DP, 就是把影响答案的信息用多维状态来表示, 什么必要什么就放在状态里.

CF 314E

给定一个长度为 \(n\) 的仅包含左括号和问号的字符串, 将问号变成左括号或右括号使得该括号序列合法, 求方案总数. 例如 \((())\) 与 \(()()\) 都是合法的括号序列.

\(n<=3000\)

括号序列问题, 往往就是把左括号看成 \(+1\), 右括号看成 \(-1\),我们只需要保证任意一个前缀大于等于 \(0\), 且总和为 \(0\), 就代表是个合法括号序列了.

令 \(dp_{i, j}\) 表示当前到第 \(i\) 个字符, 现在还有 \(j\) 个左括号.

那么分 \(3\) 种情况考虑:

• 若第 \(i+1\) 个字符是左括号, 则能转移到 \(dp_{i+1, j+1}\).

• 若第 \(i+1\) 个字符是右括号, 则能转移到 \(dp_{i+1, j-1}\).

• 若第 \(i+1\) 个字符是问号, 则能转移到 \(dp_{i+1, j-1}\) 与 \(dp_{i+1, j+1}\).

最终 \(dp_{n, 0}\) 就是方案总数啦.

\(O(n^2)\)

bzoj4922

给出一些括号序列，要求选择一些括号序列拼接成一个合法的括号序列, 使得总长最大.

\(1 \leq n \leq 300\), 表示括号序列的个数

括号序列的长度 \(len\) 不超过 \(300\).

首先对于每个括号序列, 把左边的左括号和右边的右括号对消, 最后能得到一坨这样的东西:

\())…))((…((\)

就是 \(x\) 个右括号然后 \(y\) 个左括号, 记作 \((x, y)\)

然后考虑假如我们的子集选好了, 我们要按照什么顺序拼接才能拼成一个合法的括号序列呢?

这就转化成了另一个问题:

BZOJ3709

在一款电脑游戏中, 你需要打败 \(n\) 只怪物 (从 \(1\) 到 \(n\) 编号). 为了打败第 \(i\) 只怪物, 你需要消耗 \(d_i\) 点生命值, 但怪物死后会掉落血药, 使你恢复 \(a_i\) 点生命值. 任何时候你的生命值都不能降到 \(0\) (或 \(0\) 以下)

请问是否存在一种打怪顺序, 使得你可以打完这 \(n\) 只怪物而不死掉.

\(N \leq 10^5\)

贪心, NOIp 的贪心很多都是按照某种方式排序, 然后依次选或处理.

我们来看看应该怎么排序.

• 如果 \(a_i - d_i > 0\), 说明打掉这个怪兽有血可恢复, 那么血量会变多, 明显我们按照伤害 \(d_i\) 从小到大排序即可, 然后一个个杀下来.

• 如果 \(a_i - d_i < 0\), 说明会亏血. 一个精妙的想法就是, 最后剩余的血量值, 假设是 \(x\), 那么 \(x\) 是固定的. 然后可以看作初始血量为 \(x\), 怪兽的属性 \(a\), \(d\) 交换，这样就和上一种情况一样了.

回到bzoj4922

我们还是把左括号看成 \(+1\), 右括号看成 \(-1\), 同样是保证任意一个前缀大于等于 \(0\), 且总和为 \(0\).

那就是每一个给定的序列都是 先 \(-L_i\)再 \(+R_i\), \(L_i\) 是对消后左端右括号的数量, \(L_i\) 是对消后右端左括号的数量. 然后依次拼起来之后任何一个前缀都大于等于 \(0\), 这个其实和刚刚所讲的题目完全一样.

我们按照上一题的做法排序即可, 排序后我们从左往右做 DP.

设 \(f_{i, j}\) 为前 \(i\) 个括号序列 \(-1\) 与 \(+1\) 的和为 \(j\) 个时选出括号序列最长的长度和.

也就是前 \(i\) 个括号序列左括号比右括号多 \(j\) 个时的最长的长度和.

转移时考虑下一个括号序列选不选即可.

\(Len_i\) 为排完序后第i个括号序列的长度.

最后答案就是 \(f_{n, 0}\). 复杂度 \(O(nlen^2)\)

卡特兰数

1. \(1, 2...n\) 依次进栈, 求有多少种可能的出栈序列.

2. 由 \(n\) 对括号形成的合法的括号序列由多少个?

3. \(n\) 个节点共能构成多少种二叉树, 左右子树是认为不同.

4. 凸多边形的三角划分的方案数: 把一个凸多边形用 \(n - 3\) 条直线连接 \(n - 3\) 对顶点, 共形成n-2个三角形，求方案数.

5. 一个 \(n * n\) 的格子, 从 \((0,0)\) 走到 \((n,n)\), 求不跨过 \((0,0) \Rightarrow (n,n)\) 这条直线的路径方案数.

\(N \leq 10^5\)

我们设 \(f_n\) 表示 \(n\) 个数依次进栈所能形成的出栈序列数.

似乎和之前不一样, 好像不是划分成一段一段那样的简单形式.

我们可以考虑另一种形式的状态转移方式, 以转移到子问题.

注意一段一段划分我们可以枚举最后一段的起点, 但是这里不是一段一段的, 我们要考虑另外的转移方式.

实际上我们发现我们可以枚举 \(1\) 这个数是什么时候出栈的. 那么我们可以得到:

其实还有一个更简便的形式:

一个经典题

有 \(n\) 个数, 选择其中若干数, 使得每连续 \(k\) 个数中都至少有一个数被选中, 且选出的数的和最小.

令 \(dp_i\) 表示前 \(i\) 个数满足题目要求且第 \(i\) 个数被选中, 这样的情况下选出的数的和最少是多少.

通过枚举上一个被选出的数 \(j\) 在哪里, 有:

\(O(n^2)\)

单调队列

我们合法的转移区间不断向右移动, 而这就是一个典型的滑动窗口问题.

对于两个决策 \(j_1\), \(j_2\), 满足 \(j_1 < j_2\)

若 \(dp_{j_1} < dp_{j_2}\), 则当 \(i - j_1 >k\), \(i - j_2 \leq k\)时, \(j_2\) 能代替 \(j_1\)

若 \(dp_{j_1} \geq dp_{j_2}\), 则无论何时, \(j_1\) 都不可能比 \(j_2\) 优, 可以直接删除.

每次在队列末尾插入删除一个数或者在队首删除一个数, 且该队列始终保持单调递增.

因此称为单调队列优化.

每个数进入队列出队列一次, 转移是 \(0(1)\) 的, 总时间复杂度为 \(O(n)\)

int l=1,r=0;
for (int i=1;i<=n;i++) {
  while (l<=r&&q[l]

for (int l = n; l >= l; l--)
  for (int r = l; r <= n; r++)
    if (l == r)
      dp[l][r] = 0;
    else {
      dp[l][r] = inf;
      for (int k = l; k < r; k++)
        dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]+(sum[r] - sum[l - 1]));
    }