C++ 浅谈平行四边形不等式优化DP
前言在一些DP中,三重的循环容易造成超时,那么又什么方法来优化呢? 当然有,有一种叫做平行四边形不等式的玩意优化DP 平行四边形不等式如果有两个区间满足 f[a][c]+f[b][d]<=f[b][c]+f[a][d],那么这个东东就是平行四边形不等式 可以这样理解,交叉或包含的两个区间,a到c和b到d的值满足小于等于包含的两个区间(bc包含于ad) 还有就是决策单调性? ? ? ?w[i,j]<=w[i',j'] ? ([i,j]属于[i',j']) 既 i'<=i 这玩意儿有什么性质,对边互相平行? 非也,这玩意儿有两个性质 定义一个 动态转移方程 f [ i ][ j ] = min ( f [ i ][ j ],f[ i - 1 ][ k ] + w[ k - 1 ][ j ] )? 一. 如果w满足决策单调性?????且满足平行四边形不等式那么 f?也满足四边形不等式 二. 当定理一的条件满足时,让d[i,j]取最小值的k为K[i,j],则K[i,j-1]<=K[i,j]<=K[i+1,j]? 三. w为凸当且仅当w[i,j]+w[i+1,j+1]<=w[i+1,j]+w[i,j+1]? (后两条我也不懂) DP优化有一动态转移方程?f [ i ][ j ] = min ( f [ i ][ j ],f[ i - 1 ][ k ] + w[ k - 1 ][ j ] ) ,满足平行四边形不等式,那么其决策性s[ i ] [ j ] 满足 s[ i - 1 ][ j?] <= s[ i ][ j ] <= s[ i ][ j? + 1 ],这样就可以约束 k (只用从s[ i - 1 ][ j?] 循环到s[ i ][ j? + 1 ] ,因为其最优决策性必定在这当中),减少 k 的循环次数,从而减少一重循环。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |