题目：
lanxisi带领着他的拆迁队来整治一个街道。这个街道由N个旧房子组成，从左到右编号为1..N。每个旧房子i有一个正整数的美观度Ai。
lanxisi希望整个街道从左到右美观度严格递增，也就是保证Aij（i
现在，请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费（当然是在保留旧房子最多这个前提下的）。
lanxisi希望整个街道从左到右美观度严格递增，也就是保证Aij（i
现在，请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费（当然是在保留旧房子最多这个前提下的）。
分析：
首先这种题一看要么贪心要么DP，对吧……贪心估计不靠谱，所以往DP上想。
因为需要尽可能保留旧房子，所以先考虑一个问题：假设我们保留的房子中，有两栋是i,j（i
显然，条件应该是A[i]+j-i<=A[j]，因为中间那些房子在重建后的高度至少应该是A[i]+1,...,A[i]+j-i-1（j=i+1并不影响结论）。换句话说，应该满足A[i]-i<=A[j]-j。
那就可以解决“保留最多旧房子”这个问题了：求出数列{A[i]-i}的最长不下降子序列，其长度就是最多能保留的房子数。最长不下降子序列用O(NlogN)的算法求，下面设以i为结尾的最长不下降子序列长度为g[i]。
再来考虑DP。
设f[i]表示：当前进行到i，要求留下i这个房子的最小花费。
然后考虑f[j]由什么转移而来……显然是上一个保留的房子i（j是第一栋保留的房子这种情况只需要特判一下，并不影响我们的讨论）。i应该满足什么条件？首先需要i<=A[j]-j，不过还有另外一个条件：g[i]+1=g[j]，否则就无法达到“保留最多旧房子”这个要求了。
然后我们把条件转移方程列出来。
对于决策i，它所得出的f[j]有三个部分：
①1~i的花费，即f[i]
②i+1~j的花费，即(A[i]+1)+(A[i]+2)+…+(A[i]+j-i-1)
③j的花费，即A[j]+B[j]
将它们写出来，就是这样的：
![[国家集训队2011]拆迁队 <wbr>解题报告” title=”[国家集训队2011]拆迁队 <wbr>解题报告”></a><br />
（图来自出题人的解题报告，下同）</div>
<div>
</div>
<div>有没有感到一股斜率优化的气息……括弧笑</div>
<div>于是分离变量，结果是这样的：</div>
<div><a target=](http://47.95.244.138/wp-content/uploads/2017/10/sg_trans-5.gif)