dp多维状态的优化
面对一个多维dp问题，根据维度之间联系的紧密程度，我们可以选择
1.维度之间紧密相关，只能直接枚举
2.维度之间完全无关，只是贡献通过某种形式相加，可以割裂为两个dp处理
3.介于1,2之间，不能割裂计算，但是可以将转移过程割裂为若干步来优化
e.g.1: 选区间1
问题描述
对于所有二元组(a,b, (a,bin[1,n]cap , aleq b))，给出了其权值(w_{a,b})
现在求一个元组序列(A=(a_1,b_1),(a_2,b_2),cdots)，满足(a_1<a_2,b_2<b_1)
定义(displaystyle w_A=sum w_{a_i,b_i}+sum w_{a_{i-1},a_i}+sum w_{b_{i-1},b_i}) ，最大化(w_A)
原dp
令(dp_{a,b})表示最后一个元组为(a,b)时的最大权值，状态数为(O(n^2))
直接转移复杂度为(O(n^2))，总复杂度为(O(n^4))
分布转移
两维的状态决定了权值，因此不可以割裂
但是两个维度在转移时并没有必然联系，因为只涉及(a_{i})和(a_{i+1})，(b_i)和(b_{i+1})的关系
因此可以先转移(a)这一维，然后再转移(b)这一维
具体的，转移可以描述如下
1.(dp_{a,b}+w_{a,c} ightarrow f_{c,b})
2.(f_{c,b}+w_{d,b}+w_{c,d} ightarrow dp_{c,d})
优化后转移复杂度为(O(n))，状态数虽然加倍但是不影响量级
总复杂度为(O(n^3))
e.g.2: 选区间2
问题描述
对于所有二元组(a,b, (a,bin[1,n]cap , aleq b))，给出了其权值(w_{a,b})
现在求一个元组序列(A=(a_1,b_1),(a_2,b_2),cdots)，满足(a_1<a_2,b_2<b_1)
定义(displaystyle w_A=sum w_{a_{i-1},a_i}+sum w_{b_{i-1},b_i}) ，最大化(w_A)
原dp
令(dp_{a,b})表示最后一个元组为(a,b)时的最大权值，状态数为(O(n^2))
直接转移复杂度为(O(n^2))，总复杂度为(O(n^4))
分布转移
容易发现这个问题同样适用选区间1的优化
割裂
容易发现权值由(a_i,a_{i+1})，(b_i,b_{i+1})决定，不需要知道过程中每一个(a_i,b_i)的组，只需要知道数量
而(a,b)有单调性，所以关于(aleq b)的限制只需要最后满足即可
令(f_{i,j})表示已经枚举了(i)个元素，最后一个(a_i=j)时的最大值
同理，令(g_{i,j})已经枚举了(i)个元素，最后一个(b_i=j)时的最大值
状态数为(O(n^2))，转移复杂度为(O(n))，最后可以在(O(n^2))时间内合并(f,g)的贡献
总复杂度为(O(n^3))
e.g.3: 足球
Source: COCI2012/2013 Contest#5 F
问题描述
有(2n)个人踢球，两队各(n)个人，一开始球在A队1号
每秒钟，按照一定概率球可能会被某一些对手抢走，或者传给某一些队友，或者射门
射门只有一定概率(p_i)射中，每次射门之后球会到对方1号队员
求(T)秒后比分为(a,b)的概率，如果一队得分达到(r)，视作胜利，比赛结束
为了便于分析，(O(n)=O(T),O(r)=O(sqrt n))
原dp
记录时间、比分、球的位置，状态数为(O(Tnr^2)=O(n^2r^2))
转移枚举的情况不超过(2n)，转移复杂度为(O(n))，总复杂度为(O(n^3r^2))
割裂
在记录比分的同时记录球的位置并没有意义，因为实际上关键事件实际上就是射门，每次射门之后球所在位置情况是(O(1))的
那么新的dp将 球的位置 和 比分情况 割裂开来
1.处理球的位置，令(f_{i,j,k})表示一开始球在(i)队1号时，第一次射门是在(j)时刻，由球员(k)射门（(k)可以是两队中任何一个）
状态数为(O(Tn))，转移为(O(n))，这一部分复杂度为(O(n^3))
2.比分情况
令(g_{i,j,a,b})表示(i)时刻，球在(j)队1号，当前比分为(a:b)的概率
状态数为(O(Tr^2))，转移为(O(T))，总复杂度为(O(T^2r^2))
e.g.4: 异或
Source: CSP-S 2020 初赛完善程序2 （大雾
给定长度为(n)的序列(a_iin[0,m),m=2^{16})，(nleq 10^{5})
设(w(x)= ext{pop\_count}(x)+x)，求一个子序列(b_i)
最大化(sum w(b_ioplus b_{i+1}))
原dp
令(dp_{x})表示子序列最后一个元素为(x)时的答案，状态数为(O(m))
对于每个数(a_i)，枚举前驱状态进行转移，复杂度为(O(m))
总复杂度为(O(nm))
分布转移
这道题看似是一个1维dp，但是实际上实际上权值是分位处理的
我们不如先看一个类似的选区间问题的变体
对于所有二元组(a,b, (a,bin[1,n]cap ))，给出了其权值(w_{a,b})
给定了一个元组序列(A=(a_1,b_1),(a_2,b_2),cdots)
现在要选出(A)的一个子序列(B)，定义(displaystyle w_B=sum w_{a_{i-1},a_i}+sum w_{b_{i-1},b_i}) ，最大化(w_B)
实际上这两个问题是完全相同的，但是由于限制了(a_i,b_i)为子序列，导致分布显得比较奇怪
分布转移的过程中，转移状态应该是这样的
((a_1,b_1) ightarrow (a_2, b_1) ightarrow (a_2,b_2))
容易发现这个过渡状态((a_2,b_1))实际上并不是一个存在的元组，并不满足匹配关系
那么我们如何得到这个过渡状态呢？
1.我们手里有((a_1,b_1))的dp值(dp_{a,b})
2.我们并不知道(a_2)，于是需要向所有可能的(a_2)转移，得到(f_{c,b})
(forall c,dp_{a_1,b_1}+w(b_1,c) ightarrow f_{c,b_1})
3.当拿到(a_2,b_2)时，此时我们已经知道了(a_2)，但是不知道(b_1)，因此需要从所有(b_1)中得到(dp_{a_2,b_2})的值
(forall c,f_{a_2,c}+w(c,b_2) ightarrow dp_{a_2,b_2})
分析会发现，(dp_{a,b})反而在这个过程中只是一个过渡值，并不需要开数组记录
于是就得到了完善程序的dp