はまやんはまやんはまやん

hamayanhamayan's blog

組分け / Division [第一回 アルゴリズム実技検定 過去問 G]

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;
}