决策单调性
区间包含单调性
[L leq l leq r leq R
\
w(l,r) leq w(L,R)
]
证明区间包含单调性只需证明下式即可
[w(l,r)leq w(l-1,r)
\
w(l,r)leq w(l,r+1)
]
四边形不等式
[l_1 leq l_2 leq r_1 leq r_2
\
w(l_1,r_1)-w(l_1,r_2)leq w(l_2,r_1)-w(l_2,r_2)
]
证明四边形不等式只需证明下式即可
[w(l,r)-w(l,r-1) leq w(l-1,r)-w(l-1,r-1)
]
若等号恒成立，则称其满足四边形恒等式。
一些有用的性质
(1.)任意个满足 区间包含单调性/四边形不等式 的二元函数的线性组合依然满足 区间包含单调性/四边形不等式。
(2.)若(w(l,r)=f(r)-g(l))则二元函数(w)满足四边形恒等式。当(f,g)单调递增时，(w)还满足区间包含单调性。
(3.)(h(x))是凸函数，(w(l,r))满足区间包含单调性和四边形不等式，则(h(w(l,r)))也满足四边形不等式。
(4.)(h(x))是凸函数且单调递增，(w(l,r))满足区间包含单调性和四边形不等式，则(h(w(l,r)))也满足区间包含单调性和四边形不等式。
区间dp的优化
(dp)方程形如下式：
[f[l][r]=min{ f[l][k]+f[k+1][r]) }+w(l,r)
]
若(w)满足区间包含单调性和四边形不等式，则有下定理成立
[g[l][r-1]leq g[l][r] leq g[l+1][r]
]
序列分段dp的优化
(dp)方程形如下式：
[f[i][j]=min{f[k][j-1]+w(k+1,i)}
]
若(w)满足区间包含单调性和四边形不等式，则有下定理成立
[g[i][j-1]leq g[i][j] leq g[i+1][j]
]
for(int i=1;i<=m;i++)f[n+1][i]=n-1;
for(int i=1;i<=n;i++)f[i][1]=0,dp[i][1]=w(1,i);
for(int j=2;j<=m;j++)
for(int i=n;i>=j;i--)
for(int k=f[i][j-1];k<=f[i+1][j];k++)
if(dp[i][j]>dp[k][j-1]+w(k+1,i))
{
f[i][j]=k;
dp[i][j]=dp[k][j-1]+w(k+1,i);
}