ABC119C Synthetic Kadomatsu

問題

C - Synthetic Kadomatsu

考察

解説ACです。
DFSを使う方法，bit全探索（4進数探索）を使う方法の２つがあり，今回はDFSで解きました。
探索はアルゴリズムの基本だなと改めて感じさせる問題です。

組み合わせを全探索するときの組み合わせ配列の渡し方がまだしっかり身についていません。
今回はvectorVに組み合わせを入れていきますが，メイン関数からのDFSの呼出の際にはdfs(0,vector(N))で呼び出していて，大きさと形式だけを渡しているようです。このあたりがまだいちいち確認しないと書けません。

評価関数では　ABCのいずれかがない場合に評価しないところ　合成魔法の使用数のカウント　の２つがポイントかと思います。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

//vector<int>V;
int N;
int L[8];
int A,B,C;
int a,b,c;
int cnta,cntb,cntc;
int ans=1000000;
int sum;

//評価関数
void culc(vector<int>V){
  int cnta=0;
  int cntb=0;
  int cntc=0;
  a=0;
  b=0;
  c=0;
  for(int i=0;i<V.size();i++){
    sum=0;
    if(V[i]==0){
      a+=L[i];
      cnta++;
    }
    if(V[i]==1){
      b+=L[i];
      cntb++;
    } 
    if(V[i]==2){
      c+=L[i];
      cntc++;
    }
  }
  //いずれかの材料がない場合は計算しない
  if(cnta*cntb*cntc==0) return ;
  //延長もしくは短縮魔法カウント
  sum=abs(A-a)+abs(B-b)+abs(C-c);
  //合成魔法使用数*10を加算
  sum+=(cnta+cntb+cntc-3)*10;
  ans=min(ans,sum);
  return;
}

//DFS 
void dfs(int depth,vector<int>V){
  if(depth==N){
    culc(V);
    return;
  }
  for(int i=0;i<4;i++){
    V[depth]=i;
    dfs(depth+1,V);
  }
  return;
}

int main(){
  //入力
  cin>>N;
  cin>>A>>B>>C;
  for(int i=0;i<N;i++){
    cin>>L[i];
  }
  //vectorの引数の渡し方注意
  dfs(0,vector<int>(N));
  cout<<ans<<endl;
  return 0;
}