AtCoder ABC 119 C - Synthetic Kadomatsu (300 点)

問題

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

結論

それぞれの竹を、Aに使う、Bに使う、Cに使う、使わないに分類する。その組み合わせを全探索

考えていたこと

本営の解説と同じ方針には行き着いたのですが、実装力が足らず。。。
本番ではbit全探索で実装を試みていたので、後でアプローチしてみようと思います。

#include <bits/stdc++.h>

using namespace std;

int N, A, B, C;
int l[10];


int dfs(int cur, int a, int b, int c) {
    if (cur == N) {
        if (min({a, b, c}) > 0) {
            return abs(a - A) + abs(b - B) + abs(c - C) - 30;
        } else {
            return INT_MAX - 10;
        }
    }
    int ret0 = dfs(cur + 1, a, b, c);
    int ret1 = dfs(cur + 1, a + l[cur], b, c) + 10;
    int ret2 = dfs(cur + 1, a, b + l[cur], c) + 10;
    int ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10;
    
    return min({ret0, ret1, ret2, ret3});
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> A >> B >> C;
    for (int i = 0; i < N; ++i) {
        cin >> l[i];
    }

        
    int res = dfs(0, 0, 0, 0);

    cout << res << endl;
    
    return 0;
}