hdu 3045 && POJ 3709
问题的模型是给出一个序列，要求你分成若干组，然后对于每一组，计算出组中元素与最小的那个元素之差的和，然后每个组都加起来，要求最小
这里需要对一个连续性的证明：即从小到大排，连续的分成若干组所得结果一定比离散的选取要好，这个作为引理1:要证明这个病不难，只需要对两个连续的组，从中挑出一个互换，比较，讨论较小的那个组拿出的是最小的还是其他的即可，总之可以获得证明
不难得到状态转移方程：dp[i]=min(dp[j]+sum[i]-sum[j]-a[j+1]*(i-j))
定义w[j][i]表示从状态j转移到i的转移代价，称为代价函数
(1)：对于当前的点i来说，两个决策点j<k如k比j好，那么在后面的点的选取中k始终要比j好，即w[j][i]>w[k][i]，首先dp[i]是单调非递减的，状态k如果比j好，即w[j][i]+dp[j]>w[k][i]+dp[k]
显然w[j][i]>w[k][i],那么对以i后面的一个点r，相当于再原来的基础上分别加上一个增量 
sum-a[j+1]*(r-j) 和sum-a[k+1]*(r-k),那么通过这个式子很容易得出w[j][r]>w[k][r]结论1论证
这样给了我们一个启示，对于当前不成为决策点的点来说以后都不需要转移，这个我对其称其为对后续状态影响的持续性
(2):我们再来看j,k着两个决策点 k比j好
当且仅当cost[j][i]>=cost[k][i]，化简得（cost[j][i]是指从j过来得到的状态值）
dp[j]+sum[i]-sum[j]-a[j+1]*(i-j)>=dp[k]+sum[i]-sum[k]-a[k+1]*(i-k)
(dp[k]-dp[j])-(sum[k]-sum[j])+k*a[k+1]-j*a[j+1]<=i*(a[k+1]-a[j+1])
另左边部分为G(k,j) a[k+1]-a[j+1]=S(k,j)
得到斜率方程 G(k,j)/S(k,j)<=i;注意到右边只和当前的转移点有关
故k比j好当且仅当 满足上式子，我们可以在一个决策队列的头部进行如上的剔除，使得队首的一个元素是最佳决策点，从而维护斜率的单调性，显然队首是最优的，否则可以继续出队
(3):由于一组至少有m个成员的限制，那么如果有>=2m的连续元素呢，是否会产生最优解，答案是否定的，因为如果存在这样一组，必然可以从中间某处断开，分裂成两组>=m的，且值之和不比原先的差
令i<j<k，j是断开点，对于 区间[i,j] [j+1,k]
原来的代价是sun[k]-sum[i-1]-a[i]*(k-i+1)
现在是 sum[j]-sum[i-1]-a[i]*(j-i+1)+sum[k]-sum[j]-a[j+1]*(k-j)
两者做比较做差得： -a[i]*(j-i+1)-a[j+1]*(k-j)+a[i]*(k-i+1)因为a[i]<a[j+1]
故上式子<=-a[i]*(j-i+1)-a[i]*(k-j)+a[i]*(k-i+1)<=0
得证，故对每次新的决策点进入我们总选取最远的那个，同时保证前m个都先进入
即 i-m+1>=m满足这个才进入队尾
(4)对于队尾也需要做一个维护单调性的工作
首先来看三个决策点 i<j<k r是当前的位置
G(j,i)/S(j,i) G(k,j)/S(k,j),我们要找寻的是一个类似抛物线的极值点，而这个极致点使得其肯定不如两端的决策点来的好，我们对此分类讨论：
G(j,i)<=r j比i好
情况1：G(k,j)/S(k,j)<=r k比j好 情况2 G(k,j)/S(k,j)>r j比k好
G(j,i)>r  i比j好
也就是说j不成为极值点当且仅当G(j,i)/S(j,i)>=r且 G(k,j)/S(k,j)>r这种情况
如果不出现这种情况，那么显然我们可以吧决策点j去掉，因为它破坏了斜率单调性，联想下抛物线
接下来的就是收尾工作：

对斜率优化做个总结：首先分析问题，一般可能存在正推或者逆推，如何选取呢，通常是和代价的单调性有关，或者是推出一个正确的斜率方程

然后就是证明一个决策点优略，即对后续状态影响的持续性，保证非最优点永远不可能进入决策队列
变换G函数找到一个满足式，这个G函数包括S函数，其实可以看做事一个二元决策点的变元函数，也就是说这个函数的值仅有决策点决定，他们和当前状态可能会满足一个偏序关系，这个偏序关系决定了决策点的优略，如果说没有S函数或者说与i无关，可能是个常数，那么不等关系同样适用于一般优化（个人认为），对队首和队尾分别进行一次单调性的维护，注意当前决策点的进入时间，最优决策点可能在队尾，也可能在队首，这个视具体的斜率方程而定，队首是对当前位置的斜率维护，而队尾则是对那些极点进行剔除

• 感谢，昨天就做这题，后来不懂就不想做了，今天再试试 (0) lqp18_31 2009-08-25 22:32:29
• Re:解题报告： (7) zsasuke 2009-11-16 22:25:28
• 为什么dp[i]是单调非递减的呢？ (59) SpellBreaker 2010-07-13 16:23:07