UVaOJ11218 - KTV-CSDN博客

本文链接：https://blog.csdn.net/chuan6099/article/details/8966762

本文介绍了一种针对KTV唱歌活动的人员分组算法，旨在最大化组合得分。该算法适用于9个人分成3组的情况，每组3人，通过递归搜索确定最佳组合方式。输入包括可能的组合数量及每种组合的得分，输出则是最高的总得分。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

11218 - KTV

Time limit: 3.000 seconds

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

Output for the Sample Input

Case 1: 6
Case 2: -1

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

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int group[82][4], ans, n;
bool occur[10], vis[82];
void ssearch(int cur, int tot) {
    if (cur >= 3) {
        if (tot > ans) {
            ans = tot;
            return;
        }
    }
    for (int i = 0; i < n; i ++) {
        if (! vis[i]) {
            if (occur[group[i][0]] || occur[group[i][1]] || occur[group[i][2]])
                continue;
            occur[group[i][0]] = occur[group[i][1]] = occur[group[i][2]] = true;
            vis[i] = true;
            ssearch(cur + 1, tot + group[i][3]);
            occur[group[i][0]] = occur[group[i][1]] = occur[group[i][2]] = false;
            vis[i] = false;
        }
    }
}
int main() {
    int cas = 1;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
        for (int i = 0; i < n; i ++) {
            scanf("%d%d%d%d", &group[i][0], &group[i][1], &group[i][2], &group[i][3]);
        }
        ans = -1;
        memset(occur, false, sizeof(occur));
        memset(vis, false, sizeof(vis));
        ssearch(0, 0);
        printf("Case %d: %d\n", cas ++, ans);
    }
    return 0;
}