Synthetic Kadomatsu [AtCoder Beginner Contest 119 C]

https://atcoder.jp/contests/abc119/tasks/abc119_c

解説

https://atcoder.jp/contests/abc119/submissions/4378296

与えられた操作は順番によって、状況が変化したり、損をすることが無いので、別々に考えよう。
何か全探索する所を探すと、ある竹について、どの長さを作るのに使うかが全探索できそうな感じがする。
よって、ある竹について「Aで使う」「Bで使う」「Cで使う」「使わない」の4択で全探索する。
O(4^N)となる。
この全探索はdfsを使うのがおすすめ。
dfsで1つ目の竹から順番に4択のどれかを試していく。
Nつ目の竹まで決まったら、まずは合成魔法で合成する。
あとは、各々、延長魔法と短縮魔法で目的の長さの差分だけ調整する。
これで必要なMPが算出できるので、そのうちの最小値が答え。

int N, A, B, C, L[10];
//---------------------------------------------------------------------------------------------------
int ans = inf;
int flag[8];
void dfs(int cu) {
    if (cu == N) {
        int a = 0, b = 0, c = 0;
        int ca = 0, cb = 0, cc = 0;
        rep(i, 0, N) {
            if (flag[i] == 0) a += L[i], ca++;
            else if (flag[i] == 1) b += L[i], cb++;
            else if (flag[i] == 2) c += L[i], cc++;
        }
        if (0 == ca or 0 == cb or 0 == cc) return;
        int cand = (ca-1) * 10 + (cb-1) * 10 + (cc-1) * 10;
        cand += abs(A - a) + abs(B - b) + abs(C - c);
        chmin(ans, cand);
        return;
    }
 
    rep(i, 0, 4) {
        flag[cu] = i;
        dfs(cu + 1);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B >> C;
    rep(i, 0, N) cin >> L[i];
 
    dfs(0);
    cout << ans << endl;
}