UVa102 Ecological Bin Packing

解法
瓶に入れる色を next_permutation で決め打ちする全探索。

メモ
瓶とボトルが両方３個なのでわかりにくい？という風な問題。瓶の番号なのか、色つきボトルの入力の並びの番号なのかをはっきりさせる。図に書いても良い。

#include <bits/stdc++.h>

using namespace std;

int arr[3][3]; // [number][color]

int ans;
string astr;

string const Ini = "BGC";

void solve() {
  
  string now = Ini;
  sort(now.begin(), now.end());
  do {
    int cost = 0;
    for(int i=0; i<3; i++) {
      for(int j=0; j<3; j++) {
	if(now[i] != Ini[j]) {
	  cost += arr[i][j];
	}
      }
    }
    
    if(ans > cost) {
      ans = cost;
      astr = now;
    }
    else if(ans == cost) {
      astr = min(astr, now);
    }
  } while(next_permutation(now.begin(), now.end()));
}

int main() {
  
  while(1) {
    ans = 1<<29;
    astr = "ZZZ";
    for(int i=0; i<3; i++)
      for(int j=0; j<3; j++)
	if(!(cin >> arr[i][j])) return 0;
    
    solve();
    cout << astr << " " << ans << endl;
  }
  return 0;
}