ABC119 C - Synthetic Kadomatsu (300)

C - Synthetic Kadomatsu

概要

N項の数列lを使ってA, B, Cの3数を作る。数列には次のような加工を行う。

• liに1加算する（コスト1）
• liに1減算する（コスト1）
• liとljを合体して(li + lj)の1つの項とする（コスト10）

A, B, Cを作るために必要なコストの最小値を求めよ。

制約

3 ≦ N ≦ 8
1 ≦ A, B, C ≦ 1000
1 ≦ li ≦ 1000

方針

各数列の項の使い道は「使わない」「Aに使う」「Bに使う」「Cに使う」の4通りあるため、これをすべて試して最小のコストを求める。（全探索）
ただし、A, B, Cには少なくとも1つの項を割り当てないといけないことに注意する。（入力例3がうまくいかないので気づけた）

解答

Submission #4375289 - AtCoder Beginner Contest 119

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll ans = 1e15;
ll N, A, B, C;
ll l[10];
 
void dfs(vector<int> v){
	if(v.size() == N){
		ll t = 0;
		ll t1 = 0;
		ll t2 = 0;
		ll t3 = 0;
		rep(i, N){
			if(v[i] == 1){
				if(t1 > 0) t += 10;
				t1 += l[i];
			}
 
			if(v[i] == 2){
				if(t2 > 0) t += 10;
				t2 += l[i];
			}
 
			if(v[i] == 3) {
				if(t3 > 0) t += 10;
				t3 += l[i];
			}
		}
		if(t1 == 0 || t2 == 0 || t3 == 0) return;
 
		t += abs(t1 - A);
		t += abs(t2 - B);
		t += abs(t3 - C);
 
		ans = min(ans, t);
		return;
	}
 
	rep(i, 4){
		v.push_back(i);
		dfs(v);
		v.erase(v.end()-1);
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> A >> B >> C;
	rep(i, N) cin >> l[i];
 
	vector<int> v;
	dfs(v);
 
	cout << ans << endl;
}