四边形不等式优化

约 523 个字 14 行代码 预计阅读时间 2 分钟

$f_{l,r}=\min_{k=l}^{r-1}{f_{l,k}+f_{k+1,r}}+w(l,r)$

区间包含单调性

$\forall l_1\le l_2 \le r_1 \le r_2$，$w(l_2,r_1)\le w(l_1,r_2)$

四边形不等式

$\forall l_1\le l_2 \le r_1 \le r_2$，$w(l_1,r_1)+w(l_2,r_2)\le w(l_1,r_2)+w(l_2,r_1)$

定理

如果$w(l,r)$满足区间包含单调性和四边形不等式，记$H_{l,r}$表示最优决策点，有$H_{l,r-1}\le H_{l,r}\le H_{l+1,r}$

应用

for(int len=2;len<=n;++len)
{
    for(int l=1,r=len;r<=n;++l,++r)
    {
        for(int k=H[l][r-1];k<=H[l+1][r];++k)
        {
            if(dp[l][r]>dp[l][k]+dp[k+1][r])
            {
                dp[l][r]=dp[l][k]+dp[k+1][r];
                H[l][r]=k;
            }
        }
    }
}

---

DP优化：

记忆化搜索

合并同类项

如果转移式子只和上一层有关，滚动数组

观察转移式子中各项的单调性，是否能推导出最优决策点的单调性

整除只在余数为0时变换，可以用同余聚类

遍历一棵树，设当前遍历到 $u$ 节点，有子节点 $v_1,v_2,...$，每次遍历一颗子树就把信息和前几颗子树的信息合并，放到 $u$ 上，最终总的复杂度是 $O(n^2)$。因为每对不同点对 $(x,y)$ 不会重复合并，最多 $O(n^2)$ 个不同点对

一颗树的高度小于等于树大小，所以合并复杂度如果和高度相关，不会超过 $O(n^2)$

如果DP取值是1或0，不妨把一维作为信息去处理，而不是条件

对于dp[i][j]从max(dp[i-1][j-1],dp[i-2][j-2],dp[i-3][j-3]...)转移过来的，这样对角线上的DP，每条对角线用i-j作为标识符，求DP时同时处理每条对角线前缀最大值

连续m个元素至少选2个，考虑最后两个元素选择在什么位置，可以把倒数第二个元素绝对位置，空间复杂度O(n)，优化成倒数第二个元素和倒数第一个元素的相对位置，空间复杂度O(m)。同时倒数第一个元素的位置考虑对m取模，这样第一维也优化成O(m)