DPまとめコンテスト Z - Frog 3
とりあえず漸化式をたてると次のようになる。$ dp_iを$ i番目の足場へ移動するための最小コストとする。すると次式がなりたつ。
$ dp_i = \min_{1 \le j \lt i} \left( (h_i - h_j)^2 + C + dp_j \right)
あとは、これをDPで解けばよいのだが、なにも考えずにやると、計算量が$ O(N^2)になって間に合わない。 $ dp_i = C + h_i^2 + \min_{1\le j \lt i} \left( -2h_ih_j + h_j^2 + dp_j\right)
すると、各$ jについて$ y = -2h_jx+h_j^2+dp_j\quad(j\lt i)という直線を保持しておけば、あとは$ x = h_iにおける、それぞれの直線の値のうち最小値を計算すれば$ dp_iが求まる。
ナイーブにやると計算量は変わらないが、最小値の計算時に傾きの大きく最小値を取らない直線を削除し、また直線を追加するときに凸包を形成しない直線を削除することで計算量は$ O(N)になる。
code:java
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
long C = scanner.nextLong();
for (int i = 0; i < N; i++) hi = scanner.nextInt(); long[] dp = new longN + 1; Deque<Line> deque = new LinkedList<>();
for (int i = 1; i <= N; i++) {
while (deque.size() > 1) {
Line last = deque.removeLast();
if (deque.peekLast().y(hi) > last.y(hi)) {
deque.addLast(last);
break;
}
}
if (!deque.isEmpty()) dpi = deque.peekLast().y(hi) + hi * hi + C; Line line = new Line(-2 * hi, hi * hi + dpi); while (deque.size() > 1) {
Line first = deque.removeFirst();
Line next = deque.peekFirst();
if ((first.a - next.a) * (line.b - first.b) < (line.a - first.a) * (first.b - next.b)) {
deque.addFirst(first);
break;
}
}
deque.addFirst(line);
}
}
private static class Line {
public final long a;
public final long b;
private Line(long a, long b) {
this.a = a;
this.b = b;
}
public long y(long x) {
return x * a + b;
}
}
}