POJ 3638 - Moogle

http://poj.org/problem?id=3638

概要

一直線の道に \(h\) 個の家が並んでおり、\(i\) 番目の家の位置は \(x_i\) である。 ここから \(c\) 個の家の位置を選び地図データとする。 このとき両端の家は必ず選ばれるとする。 選ばれなかった家 \(k\) の位置は、\(k\) より小さくて \(k\) から一番近い選ばれた家を \(i\) とし、 \(k\) より大きくて \(k\) から一番近い選ばれた家を \(j\) とすると (つまり \(i < k < j\) で、\(i\) と \(j\) の間に選ばれた家は一つもない)、 \(x_i + (x_j - x_i) \cdot \frac{k-i}{j-i}\) とする。

このとき、地図データと実際の家の位置の誤差の平均の最小値を答える。

制約

• \(2 \le h \le 200\)
• \(2 \le c \le h\)

解法

まず、\(i\) と \(j\) の家を選びその間のどの家も選ばなかったとき、その間の家で生じる誤差の合計値 err[i][j] を事前に計算しておく。

そして

dp[i][j] = j 個目に i 番目の家を選んだときの誤差の最小値

という DP 表を

dp[k][j+1] = min { dp[i][j] + err[i][k] } for k in i+1 .. h

と更新して dp[h-1][c-1]/h を答える。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int T;
 9   scanf("%d", &T);
10   while (T-- > 0) {
11     int H, C;
12     scanf("%d %d", &H, &C);
13     static int a[200];
14     for (int i = 0; i < H; i++) {
15       scanf("%d", &a[i]);
16     }
17 
18     static double err[200][200];
19     for (int i = 0; i < H; i++) {
20       for (int j = i+1; j < H; j++) {
21         err[i][j] = 0.0;
22         double t = double(a[j] - a[i])/double(j - i);
23         for (int k = i+1; k < j; k++) {
24           err[i][j] += fabs(a[k] - (a[i] + t*(k - i)));
25         }
26       }
27     }
28 
29     static double dp[200][200];
30     for (int i = 0; i < 200; i++) {
31       fill_n(dp[i], 200, 1e10);
32     }
33     dp[0][0] = 0.0;
34     for (int i = 0; i < H; i++) {
35       for (int j = 0; j < C-1; j++) {
36         for (int k = i+1; k < H; k++) {
37           dp[k][j+1] = min(dp[k][j+1], dp[i][j] + err[i][k]);
38         }
39       }
40     }
41     printf("%.4f\n", dp[H-1][C-1]/double(H));
42   }
43   return 0;
44 }