實機體驗,再天天抽M8老王現身說法關鍵字魅力!吉隆坡最便宜行程一覽表色令人昏 喜會女網友悲...
2012-10-07 10:27:23 人氣(240) | 回應(0) | 推薦(1) | 收藏(0) 上一篇 | 下一篇

[UVA][brute] 11218 - KTV

0
收藏
1
推薦

Problem K

KTV

One song is extremely popular recently, so you and your friends decided to sing it in KTV. The song has 3 characters, so exactly 3 people should sing together each time (yes, there are 3 microphones in the room). There are exactly 9 people, so you decided that each person sings exactly once. In other words, all the people are divided into 3 disjoint groups, so that every person is in exactly one group.

However, some people don't want to sing with some other people, and some combinations perform worse than others combinations. Given a score for every possible combination of 3 people, what is the largest possible score for all the 3 groups?

Input

The input consists of at most 1000 test cases. Each case begins with a line containing a single integer n (0 < n < 81), the number of possible combinations. The next n lines each contains 4 positive integers a, b, c, s (1 <= a < b < c <= 9, 0 < s < 10000), that means a score of s is given to the combination (a,b,c). The last case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the largest score. If it is impossible, print -1.

Sample Input

3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0

Output for the Sample Input

Case 1: 6
Case 2: -1

Rujia Liu's Present 2: A Big Contest of Brute Force


給定 9 個人, 分3人一組, 給定組合的分數, 求最大組合分數分組,
將狀態做個壓縮, 然後窮舉兩組, 直接搜尋第三組

#include <stdio.h>
int main() {
    int n, a, b, c, s;
    int i, j, cases = 0;
    while(scanf("%d", &n), n) {
        int C[512] = {}, stk[512], stkIdx = 0;
        while(n--) {
            scanf("%d %d %d %d", &a, &b, &c, &s);
            a--, b--, c--;
            i = 1<<a|1<<b|1<<c;
            if(C[i] < s) {
                if(!C[i])  stk[stkIdx++] = i;
                C[i] = s;
            }
        }
        int ans = -1, tmp;
        for(i = 0; i < stkIdx; i++) {
            for(j = i+1; j < stkIdx; j++) {
                if((stk[i]&stk[j]) == 0) {
                    if(!C[511-stk[i]-stk[j]])
                        continue;
                    tmp = C[stk[i]]+C[stk[j]]+C[511^stk[i]^stk[j]];
                    if(tmp > ans)   ans = tmp;
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ans);
    }
    return 0;
}


11218KTV
台長:Morris
人氣(240) | 回應(0)| 推薦 (1)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][bfs] 11198 - Dancing Digits
此分類上一篇:[UVA][Greedy] 10527 - Persistent Numbers

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必���)
詳全文