AOJ 2300 - Calendar Colors

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2300

概要

N 個の色の中から，距離の合計が最大になるように M 個選んだときの距離の合計を答える．

2つの色の距離は，各要素の二乗和とする．

制約

• 0 <= M <= N <= 20
• 0.0 <= L <= 100.0
• -134.0 <= a <= 220.0
• -140.0 <= b <= 122.0

解法

C(N, M) 通りしかないので全探索．

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 
 6 struct color
 7 {
 8   double L, a, b;
 9 };
10 
11 inline double sqr(double x) { return x*x; }
12 inline double operator-(const color& lhs, const color& rhs)
13 {
14   return sqr(lhs.L - rhs.L) + sqr(lhs.a - rhs.a) + sqr(lhs.b - rhs.b);
15 }
16 
17 int main()
18 {
19   int N, M;
20   cin >> N >> M;
21   vector<color> cs;
22   for (int i = 0; i < N; i++) {
23     color c;
24     cin >> c.L >> c.a >> c.b;
25     cs.push_back(c);
26   }
27 
28   double ans = 0.0;
29   for (int s = 0; s < (1<<N); s++) {
30     vector<color> v;
31     for (int i = 0; i < N; i++) {
32       if (s & (1<<i)) {
33         v.push_back(cs[i]);
34       }
35     }
36     if (v.size() != M) {
37       continue;
38     }
39 
40     double x = 0.0;
41     for (vector<color>::const_iterator it = v.begin(); it != v.end(); ++it) {
42       for (vector<color>::const_iterator jt = it+1; jt != v.end(); ++jt) {
43         x += *it - *jt;
44       }
45     }
46     ans = max(ans, x);
47   }
48   printf("%.6f\n", ans);
49   return 0;
50 }