概要
主讲教师：长沙市雅礼中学 屈运华
内容：动态规划常见模型及各种优化
主讲教师：重庆市育才中学 周祖松
内容：概率与数学期望
区间 DP
NOI1995 石子合并
Description
见题面。
Solution
设 (f_{i, j}) 合并第 (i) 堆到第 (j) 堆的最小花费。
则显然有:
枚举区间长度，再枚举起点，计算出终点，然后再枚举中间点进行转移。
复杂度 (mathcal O(n^3))。
例题 1 HDU 2476
Description
给定两个颜色序列 (A, B)，一次只能选择一种颜色粉刷一个连续的段，求把 (A) 刷成 (B) 的最少粉刷次数。
Solution
先考虑把空白序列刷成 (B)，然后再根据刷出的 (B) 计算由 (A) 刷过去的最小步数。
前半部分很好想， Luogu 上有个这半道题的原题。用这种方式进行第一遍 DP，求出 (f_{l, r})。
后半道题可以通过这种方式做：
对于一个位置 (i) 如果 (A_i) 和 (B_i) 的颜色一样，(g_{i} = g_{i - 1})。
若不同，则可以暴力枚举中转点转移：(g_i = min{f_{1, i} , min_{1 le k < i}{g_{k} + f_{k + 1, i}}})
Code
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Maxn = 1e2 + 5;
string a, b;
int f[Maxn][Maxn], f0[Maxn];
void Main() {
int L = a.length(); memset(f, 0x3f, sizeof(f));
for(int i = L; i > 0; --i) a[i] = a[i - 1], b[i] = b[i - 1];
for(int i = 1; i <= L; ++i) f[i][i] = 1;
for(int len = 2; len <= L; ++len) {
for(int l = 1; l + len - 1 <= L; ++l) {
int r = l + len - 1;
for(int k = l; k + 1 <= r; ++k) {
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] - (b[l] == b[r]));
}
}
}
for(int i = 1; i <= L; ++i) f0[i] = f[1][i];
for(int i = 1; i <= L; ++i) {
if(a[i] == b[i]) f0[i] = (i == 1 ? 0 : f0[i - 1]);
else {
for(int k = 1; k + 1 <= i; ++k) {
f0[i] = min(f0[i], f0[k] + f[k + 1][i]);
}
}
}
cout << f0[L] << '
';
}
int main() {
ios::sync_with_stdio(false);
while(cin >> a >> b) Main();
return 0;
}
例题 2 HDU 4283
本题记的题面有误，待修正
Description
给定一个序列 (d)，通过一个栈重排 (d) 中的元素顺序，最小化
的值。
Solution
待填。
二维区间 DP
例题 3 CF1199 F
Description
给定一个初始矩阵，这个矩阵上有些位置是黑色，有些位置是白色，每次可以花费一定代价将一个矩形区域令其全部变为白色，求把整个矩形变为白色的最小代价。
Solution
设 (f_{x_1, y_1, x_2, y_2}) 表示完成左上角为 ((x_1, y_1))，右下角为 ((x_2, y_2)) 的矩形的最小代价。
显然有横向上：
纵向上同理。
复杂度 (mathcal O(n^5))。转移时横纵两个方向上的枚举中转点是相互独立互不影响的。
区间 DP 的四边形不等式优化
四边形不等式：
设 (wleft(i, j ight)) 是定义在整数集合上的二元函数，如果对任意整数 (a le b le c le d)，都有 (wleft(a, c ight) + wleft(b, d ight) le w left(a, d ight) + wleft(b, c ight)) 则称 (wleft(i, j ight)) 满足四边形不等式。
区间 DP 在某个状态下的答案如果满足四边形不等式，则可以证明“中转点”的位置可以用四边形不等式优化。（这句话写得好糟糕）
附四边形不等式优化「石子合并」的代码：
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1e2 + 5;
int n;
int a[Maxn], sum[Maxn], f[Maxn][Maxn], s[Maxn][Maxn];
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; ++i) f[i][i] = 0, s[i][i] = i;
for(int len = 2; len <= n; ++len) {
for(int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
for(int k = s[l][r - 1]; k <= s[l + 1][r] && k + 1 <= r; ++k) {
int t = f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1];
if(t <= f[l][r]) f[l][r] = t, s[l][r] = k;
}
}
}
cout << f[1][n];
return 0;
}
状态压缩 DP
例题 AcWing 291 POJ2411 - 蒙德里安的梦想
Description
求一个矩形内可以用 (2 imes 1) 的矩形划分成的方案数。
Solution
维护轮廓线，设 (f_{i, j, S}) 表示决策进行到 (left(i, j ight)) 位置，当前轮廓线状态为 (S) 的方案总数。
用 (1) 表示横向方块的左半部分，用 (2) 表示纵向块的上半部分，枚举状态进行转移，复杂度 (mathcal O(2^{2n}n^2))。
单调队列优化 DP
例题 1 修剪草坪
Description
给定一个权值序列 (a), 在 (a) 中选取若干个连续段，每个段的长度都不超过给定参数 (k)，最大化段内选择的权值之和。
Solution
设 (f_{i, 0/1}) 表示前 (i) 个数中其中第 (i) 个数不选/选的最大答案。
则显然有:
其中 (s) 是前缀和，可以预处理实现。
发现 (s_i) 与 (max) 运算无关，可以提到 (max) 外面。
剩下的 (f_{j, 0} - s_{j}) 显然可以单调队列维护。
因此可以单调队列优化。
(mathcal O(n^2) o mathcal O(n))。
优化多重背包
模板题 AcWing 6 多重背包问题 III
Description
给定 (n) 种物品，每种物品有 (c_i) 个，价值为 (v_i)，体积为 (w_i)。给定一个背包体积 (V)，求在满足所选物品的总体积不超过 (V) 的情况下最大化价值和。
Solution
这题连二进制优化的 (log) 都卡，因此需要单调队列优化。
对于第 (i) 种物品，其体积为 (w_i)，发现对于某个背包体积为 (V_0) 的状态下的答案，它只能由第 (i - 1) 种物品中体积为 (V_0 - k cdot w_i(0 le k le min{c_i, lfloorfrac{V_0}{w_i} floor})) 的状态转移得到。
发现可以将状态按照 (V_0 mod w_i) 的余数进行分组，每组中的转移互不影响。
因此可以开 (w_i) 个单调队列，每个优化其按余数分组后相应组的转移。
每个状态也只有可能进入其相应组的单调队列一次。因此对于每个组转移的复杂度是 (mathcal O(V)) 的。
故总复杂度为 (mathcal O(nV))。
斜率优化
斜优/se
概率
生日悖论
有 (n) 个人，存在两个人生日相同的概率是多少？
-
当 (n > 365) 时，必然存在。（抽屉原理）
-
当 (n le 365) 时，直接算不好计算，考虑补集转化。考虑第一个人，发现第二个人与第一个人生日不同的概率为 (dfrac{364}{365})，则第三个人与前两人生日都不同的概率为 (dfrac{364}{365} imes dfrac{363}{365})，据此推导，出现生日相同的概率为：
考虑生日相同的人有多少对
想一个人相对于其他所有人的情况，那么每个人的生日是占 (dfrac{1}{365})，那么一一配对比较以后的总的概率加起来就是 (dfrac{nleft(n - 1 ight)}{365})，那么最后得出来的是：
因为是无序的，会导致算两遍，所以需要 (div 2)。
考虑有多少人生日相同，要注意，和上面的题目并不一样，就比如假设生日相同的人一共有 (3) 对，那么如果出现这三个人的生日都相同的情况，那么就是三人三对，如果是简单的用第二问的结论的变两倍正确性不高。
思考一下，首先考虑一个人的情况，概率为 (1) ，再考虑两个人，生日一共有 (365) 种，那么两个人相同的概率即为 (1-dfrac{364}{365})
那么对于 (n) 个人，可以的出来的式子就是生日相同的概率为 (1 -(dfrac{364}{365}) ^ n)
因为共有 (n) 个人 所以最终得出来的答案即为，生日相同的人一共有
数学期望
数学期望
数学期望 (Eleft(X ight) = sum left(pleft(s ight) imes Xleft(s ight) ight))
数学期望是对事件长期价值的数字化衡量。
抛硬币问题
抛 (n) 次硬币，求正面向上的期望。
有 (1) 个硬币，期望抛多少次才能出现连续的 (n) 个正面？
待填。
连续抛硬币，如果出现 (left( ext{反}, ext{正}, ext{正} ight))，我赢，出现 (left( ext{正}, ext{正}, ext{反} ight)) 则你赢，问获胜概率。
只考虑前两个即可。因为只要出现连续的两个正，你就必胜了，出现一个反，我就必胜了。
因此只有当且仅当前两个是 (left( ext{正}, ext{正} ight)) 的时候你才赢。否则我赢。所以你我获胜的概率之比为 (1 : 3)
正正反对正反反？(2:1)。
（假设ZZF是A，ZFF是B）由于获胜条件第一个是Z，可以去掉前面所有的F，如果第一个Z后是Z，那必然A赢；如果第一个Z后是F，则看第三个，第三个是F则B赢，是Z则去掉前两个ZF，从第三个Z开始，重复推理过程。设A赢的概率为x，则x=0.51（ZZ开头，必然A赢）+0.250（ZFF开头，B赢）+0.25x（ZFZ开头，递归）
——神仙学员的求解过程
抢红包问题
- 有 (n) 个红包，每个红包的钱数各不相同，你打开一个红包，看到钱数后可以选择收或丢弃。如果收了，你就不能再打开其它的红包了。如果丢弃，可以在没有打开的红包中重新选择一个打开。你只能收一个红包，丢弃的红包不能再选。问收到最大的红包的概率是多少？如何选择？
- 有 (4) 个红包，(1) 个红包里有钱，(3) 个红包是空的，我知道哪个红包有钱，而你不道，你先选中一个红包，我打开另一个空的红包，此时你可以重新选择一个红包，问你是否愿意重新选择？
答：愿意。
不换的概率 (Pleft(1 ight) = dfrac{1}{4}) （第一次就选中的概率）
换的概率 (Pleft(2 ight) = dfrac{3}{4} imes dfrac{1}{2} = dfrac{3}{8} > dfrac{1}{4})
- 有 (n) 个红包，(a) 个红包里有钱，其它红包是空的，我知道哪个红包有钱，而你不知道，你先选中一个红包，我打开 (cleft(c<n-a ight)) 个空的红包，此时你可以换一个红包，问你选中红包的概率最大是多少？
卡片收集问题
Description
买某种零食，附赠有 (n) 种卡片，每一种卡片获得的概率相同，求集齐所有卡片的期望。
Solution