a<b<c<d => w[a][c]+w[b][d]<=w[a][d]+w[b][c]
然后证明对于m同样满足
最后对于i,j选择决策点k，j-i单调，可以得到
s[i][j]<=s[i][j+1]<=s[i+1][j+1]
也就是
s[i][j-1]<=s[i][j]<=s[i+1][j]
HOJ:2952
合并石子。
dp[l,r]=dp[l,k]+dp[k+1,r]+c[i,j]
k=s[i][j - 1]..s[i+1][j]
HDU:3480
排了个序，然后就木有然后了。
HDU:2829
同上
pku:1160
dp[i][j]=i个村用j个邮局
dp[i][j] = min{dp[k][m-1]+w[k+1][m]}
注：处理的时候先循环邮局数再循环村庄数。
这样每次处理村庄i的时候，i-1和i+1都被处理过了。
Read full article from 四边形不等式优化 « Yangff's Blog
No comments:
Post a Comment