题目链接：uva 102 - Ecological Bin Packing
题目大意：有三种灯B，C，G，然后有三个箱子，每个箱子中各装有三种若干个灯，给出每个箱子中各种灯的数量。每次可以从一个箱子中移动一盏灯到另外一个箱子中，问说最少移动几次可以将灯分类，即每一个箱子中只有一种灯。注意每个箱子给出灯的顺序是B，G，C，然而输出是字典序要最小。
解题思路：暴力枚举，维护最小值以及答案即可。
#include#include const int N = 5; const char sign[5] = "BGC"; int ans, sum, v[N], t[N], c[N][N], p[N]; bool judge() { char s1[N], s2[N]; for (int i = 0; i < 3; i++) { s1[i] = sign[t[i]]; s2[i] = sign[p[i]]; } s1[3] = s2[3] = '\0'; return strcmp(s1, s2) < 0; } void dfs(int d, int s) { if (d == 3) { if (s > ans || (s == ans && judge())) { ans = s; memcpy(p, t, sizeof(t)); } return ; } for (t[d] = 0; t[d] < 3; t[d]++) { int& u = t[d]; if (v[u]) continue; v[u] = 1; dfs(d+1, s+c[d][u]); v[u] = 0; } } bool init() { sum = ans = 0; memset(v, 0, sizeof(v)); for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (scanf("%d", &c[i][j]) != 1) return false; sum += c[i][j]; } } return true; } int main () { while (init() ) { dfs(0, 0); for (int i = 0; i < 3; i++) printf("%c", sign[p[i]]); printf(" %d\n", sum - ans); } return 0; }