Minval算法分析

· · 个人记录

今天这个博客来讲Minval算法分析

minval就是将DP原本时间复杂度是O（n^3）降低至接近O（n^2）的算法，将原本数据范围不能超过300的三重循环提升至可以解决数据范围超过10000的题目

下面是思路

Minval算法证明+注释（s [ i ] [ j - 1 ] ~ s [ i + 1 ] [ j ] ）s表示区间(i , j)中的最优断点

设a , b , c , d（a<=b<=c<=d）    //结论是两边之和大于第三边（四边形）
m(a,c) + m(b,d) <= m(a,d) + m(b,c)    //四边形对边相等
s[ i ][j-1] <= s[ i ][ j ] <= s[i+1][ j ]

s[ i ][ j ]<=s[i+1][ j ]思考
d=s[ i ][ j ] ,i < i + 1 <= k < d      k<-[ i , j ]        //设d为断点位置，假设k小于d，k为i，j中任意断点                           
mk(i,j) = m(i,k) + m(k + 1,j) + sum(i,j) //表示以k为断点i，j合并的代价   sum是i到j所有值得和
md(i,j) = m(i,d) + m(d + 1,j) + sum(i,j)    //表示以d为断点i，j合并的代价（代价最小）
mk(i,j) >= md(i,j) > 0           //d为断点将i，j合并的代价最小因为d是最优断点     
=> mk(i,j) - md(i,j) > 0                            

(mk(i + 1,j) - md(i + 1,j)) - (mk(i,j) - md(i,j))         //判断k>d 或 d>k因为上面假设k<d要证明
=(mk(i + 1,j) + md(i,j)) - (md(i + 1,j) + mk(i,j))     //将系数为负数的项，系数为正数的项放在一起
=    (m(i + 1,k) + m(k + 1,j) + m(i,d) + m(d + 1,j) + sum(i,j) + sum(i + 1,j))
    - (m(i + 1,d) + m(k + 1,j) + m(i,k) + m(k + 1,j)+ sum(i,j) + sum(i + 1,j))      //将式子展开
=>将减号两边的m(k + 1,j) 和 m(d + 1,j) 和 sum(i,j) 和 sum(i + 1,j)相互消元
=(m(i + 1,k) + m(i,d)) - (m(i + 1,d) + m(i,k))
=> i<i + 1<k <d       =       a <b <c <d            //两式变量相等
=>(m(i + 1,k) + m(i,d)) - (m(i + 1,d) + m(i,k))     =     (m(b,c) + m(a,d)) - (m(b,d) + m(a,c))     >0      //因ad+bc>=ac+bd所以该式大于0
=>(mk(i + 1,j) - md(i + 1,j)) - (mk(i,j) - md(i,j)) >0            //则这个也大于0
因d<=b    则b=s[i + 1][ j ]

下面求s[ i ][j-1]的思路于上面一致，则最终得出k=s[ i ][j-1] ~ s[i-1][ j ]