https://atcoder.jp/contests/past201912-open/tasks/past201912_g
解説
https://atcoder.jp/contests/past201912-open/submissions/9253193
競技プログラミング的なやりかたで解決する。
3つ以下のグループに分けるので、全てのやり方を試してもO(3N)である。
bit全探索っぽくやってもいいし、dfsでやってもいい。
dfsが楽かも。
int N, A[10][10]; //--------------------------------------------------------------------------------------------------- int ans = -inf; vector<int> grp[3]; void dfs(int cu = 0, int tot = 0) { if (cu == N) { chmax(ans, tot); return; } rep(g, 0, 3) { int d = 0; fore(i, grp[g]) d += A[i][cu]; grp[g].push_back(cu); dfs(cu + 1, tot + d); grp[g].pop_back(); } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) rep(j, i + 1, N) { cin >> A[i][j]; A[j][i] = A[i][j]; } dfs(); cout << ans << endl; }