代码实现分支界限法解决画画问题

分支界限法（Branch and Bound）是一种求解优化问题的常用算法，它通过在搜索树中分支扩展状态空间，同时对每个扩展的状态进行剪枝，以减少搜索空间。在画画问题中，我们可以将每个可行的画法看作一个状态，通过不断分支扩展状态空间，找到能使画面得分最高的画法。

以下是画画问题的分支界限法代码实现：

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

using namespace std;

const int N = 10010;

struct Node {
    int score; // 当前画面得分
    int rest; // 剩余可用颜料数量
    int level; // 当前搜索深度（即已经涂了几个格子）
    int board[N]; // 当前画面状态
    bool operator< (const Node &t) const {
        return score < t.score; // 以得分为优先级
    }
};

int n, m, k;
int a[N][N], b[N][N], c[N][N], d[N][N];
int color[5], cost[5], value[5];
priority_queue<Node> q; // 用于存储待处理状态

// 计算当前画面得分
int calc_score(int board[]) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int cur = board[(i - 1) * m + j];
            res += value[cur] * a[i][j];
            if (i > 1 && board[(i - 2) * m + j] != cur) res += b[i][j];
            if (j > 1 && board[(i - 1) * m + j - 1] != cur) res += c[i][j];
            if (i > 1 && j > 1 && board[(i - 2) * m + j - 1] != cur) res += d[i][j];
        }
    }
    return res;
}

// 搜索过程
int solve() {
    Node cur = {calc_score(color), k, 0, {}};
    q.push(cur); // 将初始状态加入队列

    while (!q.empty()) {
        Node t = q.top(); q.pop();
        if (t.level == n * m) return t.score; // 找到最优解，返回得分

        for (int i = 1; i <= 4; i++) {
            if (t.rest - cost[i] < 0) continue; // 颜料不足，不能涂这种颜色
            int board[N];
            copy(t.board, t.board + N, board);
            for (int j = t.level + 1; j <= n * m; j++) {
                if (board[j] == 0) { // 找到空格子，涂上当前颜色
                    board[j] = i;
                    int s = calc_score(board);
                    if (s >= t.score) { // 如果得分更高，则加入队列
                        Node next = {s, t.rest - cost[i], j, {}};
                        copy(board, board + N, next.board);
                        q.push(next);
                    }
                    board[j] = 0; // 回溯
                    break;
                }
            }
        }
    }
    return 0;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m - 1; j++) {
            cin >> c[i][j];
        }
    }
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
        }
    }
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= m - 1; j++) {
            cin >> d[i][j];
        }
    }
    for (int i = 1; i <= 4; i++) {
        cin >> color[i] >> cost[i] >> value[i];
    }
    cout << solve() << endl;
    return 0;
}

在代码中，我们定义了一个 `Node` 结构体来表示每个状态，其中包括当前画面得分 `score`、剩余可用颜料数量 `rest`、当前搜索深度 `level` 和当前画面状态 `board`。我们使用一个优先队列来存储待处理状态，每次从队列中取出得分最高的状态进行扩展。

在搜索过程中，我们首先从队列中取出得分最高的状态 `t`，然后尝试使用每种颜色涂下一个空格子，并计算涂完后的得分。如果得分更高，则将新状态加入队列中。注意，在计算得分时需要考虑四个方向上相邻格子的颜色是否相同。如果搜索到一个已经涂满的画面，则认为找到了最优解，返回得分。

另外，我们还需要定义一个 `calc_score` 函数来计算当前画面的得分。具体实现细节可以参考代码中的注释。

以上就是画画问题的分支界限法算法实现。