題目鏈接：Codeforces 460E Roland and Rose

題目大意：在以原點為圓心，半徑為R的局域內選擇N個整數點，使得N個點中兩兩距離的平方和最大。

解題思路：R最大為30。那么事實上距離圓心距離最大的整數點只是12個最多，直接暴力枚舉。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>using namespace std;struct point {int x, y;point (int x = 0, int y = 0) {this->x = x;this->y = y;}
};int N, R, M, ans, pos[10], rec[10];
vector<point> vec;inline int dis (int x, int y) {return x * x + y * y;
}inline bool cmp (const point& a, const point& b) {return dis(a.x, a.y) > dis(b.x, b.y);
}void init () {scanf("%d%d", &N, &R);for (int i = -R; i <= R; i++) {for (int j = -R; j <= R; j++)  {if (i * i + j * j <= R * R)vec.push_back(point(i, j));}}ans = 0;M = min((int)vec.size(), 18);sort(vec.begin(), vec.end(), cmp);
}void dfs (int d, int f, int s) {if (d == N) {if (s > ans) {ans = s;memcpy(rec, pos, sizeof(pos));}return;}for (int i = f; i < M; i++) {int add = 0;for (int j = 0; j < d; j++)add += dis(vec[pos[j]].x - vec[i].x, vec[pos[j]].y - vec[i].y);pos[d] = i;dfs(d + 1, i, s + add);}
}int main () {init();dfs(0, 0, 0);printf("%d\n", ans);for (int i = 0; i < N; i++)printf("%d %d\n", vec[rec[i]].x, vec[rec[i]].y);return 0;
}

轉載于:https://www.cnblogs.com/wzjhoutai/p/6761329.html

總結

以上是生活随笔為你收集整理的Codeforces 460E Roland and Rose(暴力)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。