【題解】AtCoder ABC 119C – Synthetic Kadomatsu

#include <iostream>
#include <algorithm>
using namespace std;
int N, A, B, C, l[10];

int dfs(int i, int a, int b, int c){
    /*
     * i: 目前枚舉l[i]
     * a: 目標竹子#1目前的長度
     * b: 目標竹子#2目前的長度
     * c: 目標竹子#3目前的長度
     * return: 花費的MP
     */
    if (i == N){
        if (a && b && c){
            // a, b, c都不能為0 (至少使用了一些材料，才能延長或縮減長度)
            return abs(a - A) + abs(b - B) + abs(c - C);
        }else{
            return 1e9;
        }
    }
    int x[4];
    // 加法結合率(a+x)+(b+y) = (a+b)+(x+y)
    // 先枚舉合併的可能性，最後再考慮延長或縮減，O(4^N) = O(2^16) ~ O(64000)
    x[0] = dfs(i+1, a, b, c); //不使用第i段竹子
    x[1] = dfs(i+1, a + l[i], b, c) + 10; //把第i段竹子和a合併
    x[2] = dfs(i+1, a, b + l[i], c) + 10; //把第i段竹子和b合併
    x[3] = dfs(i+1, a, b, c + l[i]) + 10; //把第i段竹子和c合併
    sort(x, x+4);
    return x[0];
}

int main() {
    cin >> N >> A >> B >> C;
    for (int i = 0; i < N; i++){
        cin >> l[i];
    }
    // 拿取的第一段竹子理應零成本，但因為枚舉時採用合併法，會多算10MP
    cout << dfs(0, 0, 0, 0) - 30 << "\n";
    return 0;
}