【AOJ 2300】Calendar Colors
問題
Calender Colors | Aizu Online Judge
方針
- N個のLABカラーが与えられる.
- そこからM個取り出し, 要素それぞれの差の二乗の和を求める.
- その和の最大値が答え.
- であることから全探索しても良さそう.
- M個取り出すときにbitを使うと便利っぽい.
コード
#include <iostream> #include <vector> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,a,n) for(int i = a ; i < (int)n ; i++) struct LAB{ double l, a, b; LAB(double ln, double an, double bn){ l = ln; a = an; b = bn; } }; int main(){ int n, m; double l, a, b; vector<LAB> v; scanf("%d %d", &n, &m); rep(i, n){ scanf("%lf %lf %lf", &l, &a, &b); v.push_back(LAB(l,a,b)); } double ans = -1; rep(i, (1<<n)){ vector<LAB> elem; rep(j, n){ if(i & (1 << j)){ elem.push_back(v[j]); } } if((int)elem.size() != m) continue; double tmp = 0; rep(i, m-1){ REP(j, i+1, m){ tmp += (pow(elem[i].l-elem[j].l, 2) + pow(elem[i].a-elem[j].a, 2) + pow(elem[i].b-elem[j].b, 2)); } } ans = max(ans, tmp); } printf("%.8f\n", ans); }