POJ 2926 - Requirements

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

概要

\(N\) 個の5次元ベクトルが与えられるので，その中でマンハッタン距離が最も遠いペアを答える．

制約

解法

ベクトル \(\mathbf{x}, \mathbf{y}\) のマンハッタン距離は \(|x_1 - y_1| + |x_2 - y_2| + |x_3 - y_3| + |x_4 - y_4| + |x_5 - y_5|\) であり， 絶対値記号を外すと \(\pm x_1 \pm x_2 \pm x_3 \pm x_4 \pm x_5 \mp y_1 \mp y_2 \mp y_3 \mp y_4 \mp y_5\) となる． ここで \(x_i\) の符号に対して \(y_i\) の符号は逆である．

よって \(\pm x_1 \pm x_2 \pm x_3 \pm x_4 \pm x_5\) の符号パターン毎の最大値を計算してから， 各符号パターンに対する逆の符号パターンとの和の最大値が答えとなる．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   static const int K = 5;
 8   static const double INF = 1e15;
 9   int N;
10   scanf("%d", &N);
11   double a[1<<K];
12   fill_n(a, 1<<K, -INF);
13   for (int i = 0; i < N; i++) {
14     double xs[K];
15     for (int j = 0; j < K; j++) {
16       scanf("%lf", &xs[j]);
17     }
18     for (unsigned s = 0; s < (1<<K); s++) {
19       double y = 0;
20       for (int j = 0; j < K; j++) {
21         if (s & (1<<j)) {
22           y += xs[j];
23         } else {
24           y -= xs[j];
25         }
26       }
27       a[s] = max(a[s], y);
28     }
29   }
30 
31   double ans = -INF;
32   for (unsigned s = 0; s < (1<<K); s++) {
33     unsigned t = ~s & ((1<<K)-1);
34     ans = max(ans, a[s] + a[t]);
35   }
36   printf("%.2f\n", ans);
37   return 0;
38 }
poj/2926.cc