状态优化

状态优化

转移优化：如利用单调性、数学性质、数据结构

状态优化

一定要从具体题目入手，再去思考具体的改进方式，比如状态的表示（滚动数组，换维，状压……），状态的数量（剪枝，状态记录……）……

[USACO22DEC] Bribing Friends G

假设已经选出了朋友的集合，思考如何进行 ice cream 的分配，一定是先给 \(b\) 小的。

按 \(b\) 从小到大排序，前面一部分只用 ice cream，后面一部分只用 money 不劣，预处理前面花费 \(x\) 个 ice cream、后面花费 \(y\) 个 money 的最大答案，枚举中间一个的花费。

P5972 [PA 2019] Desant

https://www.luogu.com.cn/article/5oalg0ay

这个也是一道经典题，为什么通过数这么少？

若一个数被选择，逆序对数要加上左边已经选了且比它大的，考虑状压，记录已经选了的，但这样的状态数是 \(n2^n\)。

考虑完了前 \(i\) 个数，把 \(i\) 后面的数从小到大排序，记为 \(x_1,x_2,\dots,x_k\)，我们只关心 \([0,p_1),[p_1,p_2),\dots,[p_{k-1},p_k),[p_k,n+1)\) 有多少个数，用变进制存储状态，状态数上限是 \(n3^{\frac{n}{3}}\)。

UVA10559/POJ1390 方块消除 Blocks

发现不是很好表示区间合并后剩下的颜色和数量，那么我们何不从左到右合并呢？

可以设 \(f_{l,r,k}\) 表示区间 \([l,r]\) 的答案，同时右侧有 \(k\) 个和 \(r\) 同色的方块（非常神奇），很好转移。

ABC219H Candles

https://www.luogu.com.cn/article/pcmoygp0

正常思路状态应该有一维时间 \(t\)，但取值范围太大了。

我们可以设 \(dp_{i,j,k,0/1}\) 表示当前熄灭了 \(i-j\)，还剩 \(k\) 个要熄灭，在左/右边的最大答案，其中已经提前减去了还未熄灭的蜡烛数量乘上时间。

若有的蜡烛已经减为负数，不如不选，不会影响答案。