【題解】ZeroJudge c081: 00102 – Ecological Bin Packing

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

// Brown (0), Green (1), Clear (2)
int bin[3][3];
char color[3] = {'B', 'G', 'C'};
char ans[3];
int used[3];
map<string,int> mp;

void dfs(int idx){
    if (idx == 3) {
        int move = 0;
        for (int i=0; i<3; i++){
            for (int j=0; j<3; j++){
                if (j == ans[i]) continue;
                move += bin[i][j];
            }
        }
        string s = "";
        s = s + color[ans[0]] + color[ans[1]] + color[ans[2]];
        mp[s] = move;
        return;
    }
    for (int i=0; i<3; i++){
        if (used[i]) continue;
        used[i] = 1;
        ans[idx] = i;
        dfs(idx+1);
        used[i] = 0;
    }
}

int main() {
    int n;
    while (cin >> n) {
        bin[0][0] = n;
        for (int i=0; i<3; i++){
            for (int j=0; j<3; j++){
                if (i + j == 0) continue;
                cin >> bin[i][j];
            }
        }
        memset(used, 0, sizeof(used));
        memset(ans, -1, sizeof(ans));
        mp.clear();
        dfs(0);
        int mn = 0x7fffffff;
        for (auto i : mp){
            if (i.second < mn) mn = i.second;
        }
        for (auto i : mp){
            if (i.second == mn){
                cout << i.first << ' ' << i.second << '\n';
                break;
            }
        }
    }
    return 0;
}

def dfs(idx):
    if idx == 3:
        move = 0
        for i in range(3):
            for j in range(3):
                if j == ans[i]:
                    continue
                move += basket[i][j]
        dic[color[ans[0]] + color[ans[1]] + color[ans[2]]] = move
        return

    for i in range(3):
        if used[i]:
            continue
        used[i] = 1
        ans[idx] = i
        dfs(idx+1)
        used[i] = 0

#=== main ===
#Brown (0), Green (1), Clear (2)
color = ['B', 'G', 'C']

while True:
    try:
        N = list(map(int, input().split()))
        basket = [[0 for j in range(3)] for i in range(3)]
        for i in range(3):
            for j in range(3):
                basket[i][j] = N[i*3 + j]
        ans = [-1, -1, -1]
        used = [0, 0, 0]
        dic = {}
        dfs(0)
        mn = 1e18
        for k, v in dic.items():
            if v < mn:
                mn = v
        for k, v in sorted(dic.items()):
            if v == mn:
                print(k, v)
                break
    except:
        break