Posted on 2008-06-21 08:35
superman 閱讀(417)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 2207 C++ 00:00.00 844K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int n;
8 bool x[100][5][5];
9
10 int BestRanking;
11 int CurOrder[5], BestOrder[5]; bool choosed[5];
12
13 void search(int k, int CurRanking)
14 {
15 if(k == 5)
16 {
17 BestRanking = CurRanking;
18 memcpy(BestOrder, CurOrder, sizeof(CurOrder));
19
20 return;
21 }
22
23 for(int i = 0; i < 5; i++)
24 if(choosed[i] == false)
25 {
26 if(k == 0)
27 {
28 CurOrder[k] = i;
29
30 choosed[i] = true;
31 search(k + 1, 0);
32 choosed[i] = false;
33
34 continue;
35 }
36
37 int p, cnt = CurRanking;
38 for(p = 0; p < n; p++)
39 {
40 int t = i;
41 for(int s = 0; s < k; s++)
42 if(x[p][t][CurOrder[s]])
43 cnt++;
44 if(cnt >= BestRanking)
45 break;
46 }
47
48 if(p == n)
49 {
50 CurOrder[k] = i;
51
52 choosed[i] = true;
53 search(k + 1, cnt);
54 choosed[i] = false;
55 }
56 }
57 }
58
59 int main()
60 {
61 while(scanf("%d", &n) && n)
62 {
63 BestRanking = INT_MAX;
64 memset(x, false, sizeof(x));
65 memset(choosed, false, sizeof(choosed));
66
67 string s;
68 for(int k = 0; k < n; k++)
69 {
70 cin >> s;
71 for(int i = 0; i < 5; i++)
72 s[i] -= 'A';
73 for(int i = 0; i < 5; i++)
74 for(int j = i + 1; j < 5; j++)
75 x[k][s[i]][s[j]] = true;
76 }
77
78 search(0, 0);
79
80
81 for(int k = 0; k < 5; k++)
82 cout << char(BestOrder[k] + 'A');
83 cout << " is the median ranking with value "
84 << BestRanking << '.' << endl;
85 }
86
87 return 0;
88 }
89