一看数据，是可以爆搜的。
思路
我们看，当要涂一个矩形的时候，他上面的矩形就都要涂掉
于是我们就可以自然而然的想到拓扑
或者说我们把整个平板抽象成一个有向图，每个矩形就是一个点，他的限制就是边
比如样例：
就可以抽象成
建图就可以暴力建，才100*100的数据
然后就在图上 dfs， 枚举颜色，用拓扑去尽量涂掉这个颜色的矩形
小剪枝：记录一个rest_col，为未涂完的颜色数量。如果当前答案加rest_col大于等于最优答案，必定不行，回溯。
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define y1 yy1
#define pc putchar
using namespace std;
template<typename T>
inline void read(T &x)
{
x=0;
T f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
x*=f;
return;
}
template<typename T,typename... Args> inline void read(T &x, Args&... args){read(x); read(args...);}
template<typename Z>
inline void write(Z x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar((x%10)^48);
}
template<typename Z,typename... Args> inline void write(Z x, Args... args){write(x); putchar(' '); write(args...);}
const int COL=20+5, BLO=16+5;
const int N=10000+5;
vector<int> e[N];
void add(int x,int y){e[x].push_back(y);}
int rest_col;//还有几种颜色没涂
int block[COL][BLO];//矩形的编号，第一维是颜色，第二维是编号
int cnt_block[COL];//这个颜色的矩形有多少个
int mp[100][100];//暴力建图
int ind[BLO];//每个矩形的入度
bool paint[BLO];//这个矩形是否已经被删除了
int col[BLO];//这个矩形的颜色是什么
int rest_block[COL];//这种颜色还剩下几个矩形没有涂
int ans=0x7fffffff;
void dfs(int pos)
{
if(pos + rest_col >= ans) return;//剪枝，当前答案大于等于最优答案，必定不行
if(rest_col == 0)//全都涂完了
{
ans = pos;
return;
}
int cnt=0;
for(int c=1; c<=20 && cnt < rest_col; c++)//枚举每种颜色
{
if(cnt_block[c] == 0 || rest_block[c] == 0) continue;//这个颜色的矩形没有或者涂完了
bool can_paint = 0;//有没有能涂的
queue<int> pain/*可以涂的矩形的队列*/, del/*涂掉的矩形的队列*/, ind_upd/*更改过入度的矩形的队列*/;
for(int i=1;i<=cnt_block[c];i++)
if(!paint[block[c][i]] && ind[block[c][i]] == 0)//没被涂上色，没有入度，可以直接涂
{
can_paint = 1;
pain.push(block[c][i]);
}
if(can_paint) cnt++;
else continue;//这种色涂不上任何一个矩形
while(!pain.empty())//拓扑
{
int x = pain.front();
pain.pop();
paint[x] = 1;
del.push(x);
rest_block[c]--;
for(auto t:e[x])
{
ind[t]--;
ind_upd.push(t);
if(ind[t] == 0 && col[t] == c)//没有入度，颜色一样（不用换刷子
pain.push(t);
}
}
if(rest_block[c] == 0) rest_col--;//这种色的矩形全涂完了
dfs(pos + 1);
if(rest_block[c] == 0) rest_col++;//回溯
while(!del.empty())
{
paint[del.front()] = 0;
rest_block[c]++;
del.pop();
}
while(!ind_upd.empty())
{
ind[ind_upd.front()]++;
ind_upd.pop();
}
}
}
int n,x1,y1,x2,y2,c;
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(x1, y1, x2, y2, c);
rest_block[c]++;
col[i] = c;
if(cnt_block[c] == 0) rest_col++;
cnt_block[c]++;
block[c][cnt_block[c]] = i;
for(int x=x1;x<=x2;x++)
for(int y=y1;y<=y2;y++)
mp[x][y] = i;
}
for(int x=0;x<99;x++)
for(int y=0;y<=99;y++)
{
int pre=0, nxt=0;
if(mp[x][y] == mp[x+1][y]) continue;//同一个块
if(!mp[x][y] || !mp[x+1][y]) continue;//不存在
if(mp[x][y] != pre && mp[x+1][y] != nxt)//防止重复建边
{
pre = mp[x][y];
nxt = mp[x+1][y];
add(pre, nxt);
ind[nxt]++;
}
}
dfs(0);
write(ans);
return 0;
}