rockdu
Covered Walkway
Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1548 Accepted Submission(s): 623
Problem Description
Your university wants to build a new walkway, and they want at least part of it to be covered. There are certain points which must be covered. It doesn’t matter if other points along the walkway are covered or not.
The building contractor has an interesting pricing scheme. To cover the walkway from a point at x to a point at y, they will charge c+(x-y)2, where c is a constant. Note that it is possible for x=y. If so, then the contractor would simply charge c.
Given the points along the walkway and the constant c, what is the minimum cost to cover the walkway?
The building contractor has an interesting pricing scheme. To cover the walkway from a point at x to a point at y, they will charge c+(x-y)2, where c is a constant. Note that it is possible for x=y. If so, then the contractor would simply charge c.
Given the points along the walkway and the constant c, what is the minimum cost to cover the walkway?
Input
There will be several test cases in the input. Each test case will begin with a line with two integers, n (1≤n≤1,000,000) and c (1≤c≤109), where n is the number of points which must be covered, and c is the contractor’s constant. Each of the following n lines will contain a single integer, representing a point along the walkway that must be covered. The points will be in order, from smallest to largest. All of the points will be in the range from 1 to 109, inclusive. The input will end with a line with two 0s.
Output
For each test case, output a single integer, representing the minimum cost to cover all of the specified points. Output each integer on its own line, with no spaces, and do not print any blank lines between answers. All possible inputs yield answers which will fit in a signed 64-bit integer.
Sample Input
10 5000 1 23 45 67 101 124 560 789 990 1019 0 0
Sample Output
30726
Source
Recommend
liuyiding
一直很好奇斜率优化是个什么玩意，终于下决心要学一学。这里要特别感谢Scarlyw大佬的亲情相助。
斜率优化其实就是对于一种特殊的dp可以用单调队列维护最优状态。比如对于这道题来说，其实很简单的就可以写出状态转移方程：dp[i] = min{dp[j] + (sum[i] - sum[j + 1])^2 + c}。但是一看数据范围1e6，n^2原地螺旋起飞。
但是我们发现对于一组x1 > x2 且 x1 优于 x2 时（
dp[j] + (sum[i] - sum[j + 1])^2 + c
(j = x2) >
dp[j] + (sum[i] - sum[j + 1])^2 + c
(j = x1)）可以有括号内不等式移项展开得到下列关系：
设g(x) = dp[x] + sum^2[x + 1];那么k(x1, x2) = (g[x1] - g[x2])/(sum[x1 + 1] - sum[x2 + 1]) < 2 * sum[i]（其中i为当前状态）
这是不是有一点斜率的感觉？更加惊喜的是，x是单调的，dp数组也是单调的，又因为sum单调增，所以当然可以用单调队列维护可供转移的状态了——在队列中使两两元素的k值单调增。当我们每一次转移前，首先把队列前两个元素的k求出来，如果大于等于当前2 * sum[i]就弹出，一直到符合要求为止。这样操作后队首元素一定是最优转移（由于单调性）。当我们每一次转移之后，把 要入队的元素与队尾元素的斜率 和 队尾元素跟倒数第二个元素的斜率比较 ，也是一直弹出直到符合单调性为止。于是我们用O(n)维护单调队列换来了O(1)的最优决策查询，总复杂度O(n)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5;
long long sum[maxn], dp[maxn], q[maxn], f, b, n, c;
double calc(int x1, int x2) {
return ((dp[x1] + sum[x1 + 1] * sum[x1 + 1]) - (dp[x2] + sum[x2 + 1] * sum[x2 + 1]))/
double(sum[x1 + 1] - sum[x2 + 1]);
}
int main(){
while(1) {
f = 0, b = 1;
scanf("%lld%lld", &n, &c);
if(n == 0 && c == 0) return 0;
for(register int i = 1; i <= n; ++i)
scanf("%lld", &sum[i]);
memset(dp, 0x7f, sizeof(dp));
dp[0] = 0;dp[1] = c;q[0] = 0, q[1] = 1;
for(register int i = 2; i <= n; ++i) {
while(f < b && calc(q[f], q[f + 1]) < 2 * sum[i]) ++f;
dp[i] = dp[q[f]] + (sum[i] - sum[q[f] + 1]) * (sum[i] - sum[q[f] + 1]) + c;
while(f < b && calc(q[b], i) <= calc(q[b], q[b - 1])) --b;
q[++b] = i;
}
printf("%lld\n", dp[n]);
}
return 0;
}
没有帐号? 立即注册