思路：搜索

由于该题的数据规模很小，并且搜索空间也在可接受范围内，因此可以考虑搜索解答。

搜索过程中，枚举选择哪一位英桀作为奖励，并记录其奖励次数。之后逐层往下搜，直到所有关卡挑战完毕，更新答案。再回溯时，将上次选择的英桀次数减一，并再次选其它即可。

代码

java

import java.util.Scanner;

public class Main {
    static int n, m; 
    static int[] c, cnt;
    static int[][] a, b;

    // 输入函数
    public static void input() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        c = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            c[i] = sc.nextInt();
        }
        a = new int[n][3];
        b = new int[n][3];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 3; ++j) {
                a[i][j] = sc.nextInt();
                b[i][j] = sc.nextInt(); // 合并a和b数组的输入循环
            }
        }
        cnt = new int[m + 1];
    }

    // 深度优先搜索函数
    public static long dfs(int u) {
        if (u >= n) {
            return 0;
        }
        long ans = 0;
        for (int i = 0; i < 3; ++i) {
            int index = b[u][i];
            cnt[index]++;
            long t = a[u][i];
            if (cnt[index] == 3) {
                t += c[index];
            }
            ans = Math.max(ans, dfs(u + 1) + t);
            cnt[index]--; // 回溯
        }
        return ans;
    }

    // 主函数
    public static void main(String[] args) {
        input();
        System.out.println(dfs(0));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m; // 定义变量n和m
vector<int> c, cnt; // 定义向量c和cnt
vector<vector<int>> a, b; // 定义二维向量a和b

// 输入函数
void input() {
    cin >> n >> m; // 输入n和m的值
    c.resize(m + 1); // 调整c的大小为m+1
    for (int i = 1; i <= m; ++i) {
        cin >> c[i]; // 输入c数组的值
    }
    a.resize(n, vector<int>(3)); // 调整a的大小为n行3列
    b.resize(n, vector<int>(3)); // 调整b的大小为n行3列
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j]; // 输入a数组的值
        }
        for (int j = 0; j < 3; ++j) {
            cin >> b[i][j]; // 输入b数组的值
        }
    }
    cnt.resize(m + 1); // 调整cnt的大小为m+1
}

// 深度优先搜索函数
long long dfs(int u) {
    if (u >= n) {
        return 0; // 递归终止条件，当u大于等于n时返回0
    }
    long long ans = 0; // 定义结果变量
    for (int i = 0; i < 3; ++i) {
        cnt[b[u][i]]++; // 更新cnt数组
        long long t = a[u][i]; // 将a[u][i]赋值给t
        if (cnt[b[u][i]] == 3) {
            t += c[b[u][i]]; // 如果cnt[b[u][i]]等于3，t加上c[b[u][i]]
        }
        ans = max(ans, dfs(u + 1) + t); // 递归调用dfs函数，更新ans的值
        --cnt[b[u][i]]; // 回溯，恢复cnt数组的状态
    }
    return ans; // 返回最终结果
}

// 主函数
int main() {
    input(); // 调用输入函数
    cout << dfs(0) << endl; // 输出dfs函数的结果
    return 0;
}

题目内容

米小游正在挑战往事乐土，往事乐土中有$n$个关卡，$m$位英桀，挑战完每个关卡后可以在三位不同英桀给出的奖励中选择一个，每个奖励的能力值位$a_i$，来源位第$b_i$位英桀。

若米小游至少获得三个来源为同一位英桀的奖励，他可以获得来自这位英桀的额外奖励，能力值位$c_i$。

米小游想知道，他挑战完这$n$个关卡最多可以获得多少能力值？

输入描述

第一行输入两个整数$n,m$($3≤n，m≤13$)，表示管卡数量，英桀数量。

第二行输入$m$个整数$c_i$($0≤c_i≤10^9$)，表示每位英桀的额外奖励。

接下来对于每一个关卡：

第一行输入三个整数$a_i$($0≤a_i≤10^9$)，表示奖励的能力值。

第二行输入三个整数$b_i$($1≤b_i≤m$),表示奖励的来源，保证三个数字互不相同。

输出描述

输出一个整数表示答案

样例1

输入

4 13
0 1111 525 1031 55 0 0 722 0 430 1221 29 711
9 5 3
3 2 4
2 3 7
2 11 5
4 0 6
10 2 13
10 5 196
1 12 8

输出

1314

说明

在第$1$个关卡中，选择第$2$位英桀的奖励，获得$5$点能力值；

在第$2$个关卡中，选择第$2$位英桀的奖励，获得$2$点能力值；

在第$3$个关卡中，选择第$2$位英桀的奖励，获得$0$点能力值；3

此时米小游获得了$3$个第$2$位英桀的奖励，额外获得了$1111$点能力值；

在第$4$个关卡中，选择第$8$位英桀的奖励，获得196$点能力值；

最后的能力值为：5+2+0+1111+196=1314