动态规划

• 通过发掘转移时最优解的必要条件往往能使抽象的转移条件变得简单。
• 当问题有多维的限制时，将其中一维排序往往能简化状态设计和转移。

矩阵快速幂优化 DP

• 以下面的顺序计算矩阵乘法，访问内存连续，效率最高。

	friend inline matrix operator * (const matrix &a, const matrix &b)
	{
		matrix c;
		c.Clear(a.gn, b.gm);
		for (int i = 0; i < a.gn; ++i)
			for (int k = 0; k < a.gm; ++k)
			{
				int s = a.g[i][k];
				for (int j = 0; j < b.gm; ++j)
					c.g[i][j] = (1ll * s * b.g[k][j] + c.g[i][j]) % mod;
			}		
		return c;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

单调队列优化 DP

典例 POJ3017

• 设 $f_i$ 表示将前 $i$ 个数分成若干段、满足每段所有数的和不超过 $M$ 时各段最大值之和的最小值。不难得到转移：
  f i = min ⁡ 0 ≤ j < i 且 ∑ k = j + 1 i a k ≤ M { f j + max ⁡ j + 1 ≤ k ≤ i { a k } } f_i = \min\limits_{0\le j < i且\sum\limits_{k =j+1}^{i}a_k\le M}\{f_j + \max\limits_{j + 1\le k\le i}\{a_k\}\} fi​=0≤j<i且k=j+1∑i​ak​≤Mmin​{fj​+j+1≤k≤imax​{ak​}}
• 容易证明，最优解需满足以下两个条件之一：
  • a j = max ⁡ j ≤ k ≤ i { a k } a_j = \max\limits_{j\le k\le i}\{a_k\} aj​=j≤k≤imax​{ak​}
  • $\sum _{k=j}^i{a}_k>M$
• 第一个条件可以维护一个决策点 $j$ 单调递增、数值 $a_j$ 单调递减的队列，并用数据结构维护最优转移，这里使用的是懒惰删除的二叉堆，第二个条件只需要维护单个指针单独转移即可。

	l = 0, ql = 1, qr = 0;
	for (int i = 1; i <= n; ++i)
	{	
		while (l < i && sum[i] - sum[l] > M)
			++l;
		while (ql <= qr && sum[i] - sum[que[ql]] > M)
			val[que[ql++]] = -1;
		while (ql <= qr && a[que[qr]] <= a[i])
			val[que[--qr]] = -1;
		if (ql <= qr)
			q.push(point(val[que[qr]] = f[que[qr]] + a[i], que[qr]));
		que[++qr] = i;
		f[i] = f[l] + a[que[ql]];
		while (!q.empty() && val[q.top().t] != q.top().s)
			q.pop();
		if (!q.empty())
			CkMin(f[i], q.top().s);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

多重背包

• 给定 $n$ 种物品，其中第 $i$ 种物品的体积为 $v_i$，价值为 $w_i$，有 $c_i$ 个。
• 求能够放入容积 $m$ 的背包的物品的最大价值总和。

二进制拆分法

• 求出 $\sum _{k=0}^p{2}^k\le c_i$ 最大的 $p$，令 $r_i=c_i-\sum _{k=0}^p{2}^k$。
• 将数量为 $c_i$ 的第 $i$ 种物品拆成 $p+2$ 种物品，其体积分别为：
  $$2^0{v}_i,2^1{v}_i,\dots ,2^p{v}_i,r_i{v}_i$$
• 时间复杂度 $\mathcal{O}(nm\log c)$，其中 c = max ⁡ 1 ≤ i ≤ n { c i } c = \max\limits_{1\le i\le n}\{c_i\} c=1≤i≤nmax​{ci​}。

单调队列优化

• 将容积那一维按照模 $v_i$ 的余数分类，则可利用单调队列优化。
• 时间复杂度 $\mathcal{O}(nm)$。

斜率优化 DP

• 形如下式的转移宜采用斜率优化：
  f i = max ⁡ / min ⁡ { f j + A ( i ) B ( j ) + C ( i ) + D ( j ) } f_i = \max/\min\{f_j + A(i)B(j) + C(i)+D(j)\} fi​=max/min{fj​+A(i)B(j)+C(i)+D(j)}
  其中 $A,B,C,D$ 分别为含对应变量的多项式，$A,B$ 中的最高次数为一次。
• 去除 $\max /\min$ 的限制，移项得到：
  $$-A(i)B(j)+f_i-C(i)=f_j+D(j)$$
  将每个可能的决策 $(B(j),f_j+D(j))$ 视作平面上的一点，最优决策即用固定斜率 $-A(i)$ 的直线去截这些点，最大化/最小化截距，因而只需要维护这些点的上凸壳/下凸壳。
• 维护的方式视具体情况而定：
  • 若 $A(i),B(j)$ 均单调，用单调队列/单调栈维护即可。
  • 若 $A(i),B(j)$ 其中一个单调，将单调的那个变量视作决策点（若只有 $A(i)$ 单调则需要倒着转移），求最优决策时在凸壳上二分即可。
  • 若 $A(i),B(j)$ 均不单调，则需要用平衡树维护凸壳或离线后 $\text{CDQ}$分治。

决策单调性

四边形不等式

• $w(x,y)$ 为定义在整数集合上的二元函数，对于定义域上的任意整数 $a,b,c,d$，其中 $a\le b\le c\le d$，都有 $w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$，称为函数 $w$ 满足四边形不等式。

一维决策单调性

• 在状态转移方程 f i = min ⁡ 0 ≤ j < i { f j + w ( j , i ) } f_i = \min\limits_{0 \le j < i}\{f_j + w(j,i)\} fi​=0≤j<imin​{fj​+w(j,i)} 中，若函数 $w$ 满足四边形不等式，则 $f$ 具有决策单调性。
• 用队列维护若干个三元组 $(l,r,j)$，表示 $[l,r]$ 内的最优决策均为 $j$。
• 在队尾插入时：
  • 若比前一个三元组整个区间内的决策都优，则直接合并，继续检查前一个三元组。
  • 若比前一个三元组整个区间内的决策都不优，则直接插入队尾。
  • 否则在区间上二分找到分界点，修改两个区间的分界后插入队尾。

二维决策单调性

• 在状态转移方程 f i , j = min ⁡ i ≤ k < j { f i , k + f k + 1 , j + w ( i , j ) } f_{i,j} = \min\limits_{i \le k < j}\{f_{i,k}+f_{k+1,j}+w(i,j)\} fi,j​=i≤k<jmin​{fi,k​+fk+1,j​+w(i,j)} 中，若下面三个条件成立：
  • 可规定 $f_{i,i}=w(i,i)=0$。
  • $w$ 满足四边形不等式。
  • 对于任意的 $a\le b\le c\le d$，有 $w(a,d)\ge w(b,c)$。
• 则 $f$ 也满足四边形不等式，设 $p_{i,j}$ 表示令 $f_{i,j}$ 取到最小值的 $k$ 值，则恒有 $p_{i,j-1}\le p_{i,j}\le p_{i+1,j}$。
• 因此我们在转移时只需枚举 $[p_{i,j-1},p_{i+1,j}]$ 内的 $k$，对于长度为 $L+1$ 的区间，总枚举量为：
  $$(p_{2,L+1}-p_{1,L})+(p_{3,L+2}-p_{2,L+1})+\cdots +(p_{n-L+1,n}-p_{n-L,n-1})=p_{n-L+1,n}-p_{1,L}$$
• 因此总的时间复杂度为 $\mathcal{O}(\sum _{i=1}^{n-1}(p_{n-i+1,n}-p_{1,i}))=\mathcal{O}(n^2)$。

GarsiaWachs 算法

• 上述二维决策单调性能解决的石子合并问题有一种专门的非动态规划算法。
• 设第 $i$ 堆石子的数目为 $a_i$，令 $a_0=a_{n+1}=+\infty$，具体步骤如下：
  • 找到满足 $a_{k-1}<a_{k+1}$ 最大的 $k$。
  • 找到满足 $a_j>a_{k-1}+a_k$ 且 $j<k$ 的最大的 $j$。
  • 删除 $a_{k-1},a_k$，在 $a_j$ 后插入 $a_k+a_{k-1}$。
  • 重复上述过程直至石子被合并为一堆。
• 空间复杂度 $\mathcal{O}(n)$，时间复杂度 $\mathcal{O}(n^2)$，可用平衡树优化至 $\mathcal{O}(n\log n)$。

证明 待补充。

	read(n);
	v.push_back(Maxn);
	for (int i = 1, x; i <= n; ++i)
	{
		read(x);
		v.push_back(x);
	}
	v.push_back(Maxn);
	while (n > 1)
	{
		int j, k;
		for (k = 1; k <= n; ++k)
			if (v[k - 1] < v[k + 1])
				break ;
		for (j = k - 1; j >= 0; --j)
			if (v[j] > v[k - 1] + v[k])
				break ;
		int sum = v[k - 1] + v[k];
		v.erase(v.begin() + k - 1);
		v.erase(v.begin() + k - 1);	
		v.insert(v.begin() + j + 1, sum);
		ans += sum;
		--n;
	}
	printf("%d\n", ans);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

计算几何

欧拉公式

• 在任何一个规则球面地图上，定义 $R$ 为区域个数，$V$ 为顶点个数，$E$ 为边界个数，则恒有：
  $$R+V-E=2$$
• 推论 凸正多面体有且仅有 5 种。

证明 取凸正多面体一个顶点，设其向外有 $n(n\ge 3)$ 条棱，再取凸正多面体一个面，设其为正 $m(m\ge 3)$ 边形。一个顶点附近的角之和必须小于 $360^{\circ }$，则有：
$$n(180-\frac{360}{m})<360\iff 1-\frac{2}{m}<\frac{2}{n}$$
已知 $E=\frac{nV}{2}=\frac{mR}{2}$，代入欧拉公式即可解出 $R,E,V$。
符合条件的 $m,n$ 的解只有五组，如下图所示。

• 设棱长为 $a$，五种凸正多面体的各项数据如下（棱切球即过各边中点的球）。