参考了I_AM_HelloWord的代码，\(f[i][j]\)表示转态\(i\)时最后一刷为\(j\)的最小代价，上面的块可用暴力填涂，注意边界
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Fill(a,b) memset(a,b,sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define QWQ
#ifdef QWQ
#define D_e(x) cout << (#x) << " : " << x << "\n"
#define D_e_Line printf("\n----------------\n")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt","w", stdout)
#define Pause() system("pause")
#define TIME() fprintf(stderr, "TIME : %.3lfms\n", clock() / CLOCKS_PER_SEC)
#endif
struct FastIO {
template<typename ATP> inline FastIO& operator >> (ATP &x) {
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x =x * 10 + (c ^ '0'), c = getchar();
x = f == 1 ? x : -x;
return *this;
}
} io;
using namespace std;
template<typename ATP> inline ATP Max(ATP x, ATP y) {
return x > y ? x : y;
}
template<typename ATP> inline ATP Min(ATP x, ATP y) {
return x < y ? x : y;
}
#include <assert.h>
const int N = 21;
int lx[N], ly[N], rx[N], ry[N], tot[N], col[N], f[1 << 17][N], sta[N][N], mp[N][N];
inline bool Check(int x, int s) {
bool flag = true;
R(i,1,tot[x]){
// D_e(sta[x][i] - 1);
assert(sta[x][i] - 1 >= 0);
flag &= ((s >> (sta[x][i] - 1)) & 1);
if(flag == false) return false;
}
return true;
}
int main() {
int n;
io >> n;
R(i,1,n){
io >> lx[i] >> ly[i] >> rx[i] >> ry[i] >> col[i];
R(x,lx[i],rx[i] - 1){
R(y,ly[i],ry[i] - 1){
assert(x >= 0 && y >= 0);
mp[x][y] = i;
}
}
}
R(i,1,n){
if(!lx[i]) continue;
--lx[i];
R(j,ly[i] + 1, ry[i]){
if(mp[lx[i]][j] != mp[lx[i]][j - 1]) sta[i][++tot[i]] = mp[lx[i]][j - 1];
}
if(mp[lx[i]][ry[i]] == mp[lx[i]][ry[i] - 1]) sta[i][++tot[i]] = mp[lx[i]][ry[i] - 1];
}
Fill(f, 0x3f);
R(i,1,20) f[0][i] = 1;
int maxn = (1 << n) - 1;
R(s,1,maxn){
R(i,1,n){
if(((s >> (i - 1)) & 1) && Check(i, s)){
R(j,1,20){
if(j == col[i]) continue;
assert((s ^ (1 << (i - 1))) >= 0);
f[s][col[i]] = Min(f[s][col[i]], f[s ^ (1 << (i - 1))][j] + 1);
}
f[s][col[i]] = Min(f[s][col[i]], f[s ^ (1 << (i - 1))][col[i]]);
}
}
}
int ans = 2147483647;
R(i,1,20) ans = Min(ans, f[maxn][i]);
printf("%d", ans);
return 0;
}
/*
7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2
*/
