ABC 119 C Synthetic Kadomatsu
合成したりなんだりで規定の値を得る問題。
今回は本数がたったの八本だったので全列挙を考える。C問くらいまでは全列挙できるのも多いのでまずは全列挙を疑うべきですね。
全列挙の方法にはbit全列挙を選択。使わない、Aに使う、Bに使う、Cに使うの4状態がそれぞれについて考えられるので、2bit×N桁を用意してそれについて全列挙です。
下位桁を3と&を取ることで、どこに使うかという状態を取得しています。また、接合回数も考える必要があるので、これを記録する配列を確保。
このとき{-1,-1,-1}という配列を用意して、それぞれをA,B,Cに使った本数とすると0以上のとき10*それぞれの値で接続コストが求められるのでこの実装です。
尚、1本も使わない0の状態から伸ばしては行けないというのを見落としていたので、その処理を後からぶちこんでいてちょっと汚いです。
int main(void){ int N,A,B,C; scanf("%d %d %d %d",&N,&A,&B,&C); vector<int> l; for (int i =0; i < N; ++i){ int temp; scanf("%d",&temp); l.push_back(temp); } long long ans = 100000000000000000000; for (int i = 0; i < pow(4,N); ++i){ vector<int> temp(3,0); vector<int> joint(3,-1); int copy = i*1; for (int j = 0;j<N;++j){ int s=0; s += copy&3; copy = copy >> 2; if (s==0){ continue; }else{ temp[s-1]+=l[j]; joint[s-1]+=1; } } if (temp[0]==0||temp[1]==0||temp[2]==0){ continue; } int cost =0; cost += abs(A-temp[0]); cost += abs(B-temp[1]); cost += abs(C-temp[2]); for (int k = 0; k <3; ++k){ if (joint[k] > 0){ cost += joint[k]*10; } } if (cost < ans){ ans = cost; } } cout << ans << endl; };