平板涂色

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1593 字
状压 DFS 加记忆化，同色矩形一次涂完
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1445
// 题意：N 个互不重叠的矩形各有颜色，只有当紧靠它上方的矩形都涂完才能涂它，一次拿刷子可涂完当前所有可涂的同色矩形，求最少拿刷子次数。
// 思路：状态压缩 DFS + 记忆化。
// 1. 预处理每个矩形的「上方遮挡集合」pre[i]，用位掩码表示必须先涂哪些矩形。
// 2. 搜索时枚举颜色，把该颜色下所有前置已满足的矩形一次性涂完（同色一起涂一定不更差）。
// 3. 用 (已涂集合, 上次颜色) 做记忆化，避免重复搜索。
// 复杂度：O(2^N * C * N) 时间 / O(2^N * C) 空间
// 易错点：判断「紧靠上方」要比较 y 坐标相接并且 x 区间有重叠，只比较 y 会漏依赖关系。
// 易错点：换颜色才算新拿一次刷子，与上次颜色相同则不加次数，初始上次颜色要设成不存在的 0。
#include <bits/stdc++.h>
using namespace std;
struct Rect {
    int y1, x1, y2, x2, c;
};
int n, full;
vector<Rect> r;
vector<int> pre;
vector<int> memo;
const int INF = 1e9;
int dfs(int mask, int lastColor){
    if(mask == full) return 0;
    int& res = memo[mask * 21 + lastColor];
    if(res >= 0) return res;
    res = INF;
    for(int col = 1; col <= 20; col++){
        int add = 0;
        for(int i = 0; i < n; i++){
            if((mask >> i) & 1) continue;
            if(r[i].c != col) continue;
            if((pre[i] & mask) == pre[i]) add |= 1 << i;
        }
        if(!add) continue;
        res = min(res, dfs(mask | add, col) + (col != lastColor ? 1 : 0));
    }
    return res;
}
int main(){
    if(!(cin >> n)) return 0;
    r.resize(n);
    for(int i = 0; i < n; i++) cin >> r[i].y1 >> r[i].x1 >> r[i].y2 >> r[i].x2 >> r[i].c;
    pre.assign(n, 0);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            if(r[j].y2 == r[i].y1 && max(r[i].x1, r[j].x1) < min(r[i].x2, r[j].x2)) pre[i] |= 1 << j;
        }
    }
    full = (1 << n) - 1;
    memo.assign((1 << n) * 21, -1);
    cout << dfs(0, 0) << "\n";
    return 0;
}
平板涂色

正文

一本通·提高篇的其它内容
