题解：P13237 [GCJ 2015 Finals] Merlin QA

· · 题解

P13237 [GCJ 2015 Finals] Merlin QA题解

题目传送门

我们不难发现，对于每种原材料的排列顺序，咒语对原材料的贡献是否计入最终价值取决于该咒语在排列中的位置。("相当于对于每个原材料,取一个极大的后缀和计入答案"—— gzy语)

此题 m 很小，启示我们做全排列。

我们可以枚举所有原材料的排列顺序，对于每种排列，计算每个咒语在可能的前缀组合下的最大贡献，并求和得到总价值，最终取最大值。

生成所有原材料的排列顺序，用于枚举所有可能的咒语贡献计算方式。 dfs 全排列，或者直接用 next_permutation 函数，时间复杂度为 O(m!).

然后对于每种排列，计算每个咒语在所有可能的前缀长度下的最大贡献，累加得到该排列下的总价值，前缀长度为 1—n ,所以时间复杂度为 O(m \times n)。

总复杂度为 O(m! \times m n).

AC Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
const int M = 10, N = 105;
int t, n, m, ans = 0;
int box[M];  
bool st[M];  
int spells[N][M];  

// 快读
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

// 快写
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

void init() {
    ans = 0;
    memset(st, 0, sizeof st);
}

void dfs(int x) {
    if (x == m + 1) {
        int res = 0;
        // 对每个咒语计算最大贡献
        for (int i = 1; i <= n; i++) {
            int sum = 0, max_value = -0x3f3f3f3f;

            // 遍历所有可能的前缀长度
            for (int j = 0; j <= m; j++) {
                if (j > 0) {
                    // 加上当前原材料的贡献
                    sum += spells[i][box[j]];
                }
                if (sum > max_value) {
                    max_value = sum;  // 更新最大值
                }
            }
            res += max_value;  // 累加当前咒语的最大贡献
        }
        if (res > ans) {
            ans = res;  // 更新全局最大值
        }
        return;
    }

    // 生成排列
    for (int i = 1; i <= m; i++) {
        if (!st[i]) {
            st[i] = true;     
            box[x] = i;        
            dfs(x + 1);       
            st[i] = false;    
        }
    }
}

int main() {
    t = read();

    for (int turn = 1; turn <= t; turn++) {
        init();
        n = read();  
        m = read(); 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                spells[i][j] = read();
            }
        }

        dfs(1);  
        printf("Case #%d: ", turn);
        write(ans);
        putchar('\n');
    }
    return 0;
}
(特别鸣谢：超级无敌宇宙第一帅的十分风流倜傥潇洒高富帅年轻富裕反正就是特别幸运特别厉害的大群主巨佬gzy老师)

彩蛋：