[国家集训队2011]拆迁队 解题报告

题目:

lanxisi带领着他的拆迁队来整治一个街道。这个街道由N个旧房子组成,从左到右编号为1..N。每个旧房子i有一个正整数的美观度Ai

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]
将它们写出来,就是这样的:

发表评论

电子邮件地址不会被公开。 必填项已用*标注