P1283 平板涂色
数据范围也太小了qwq。。适合本萌新暴搜
小小的剪枝：
1.用pre预处理出每块矩形上方的矩形，pre[i][0]记录数目（如果数据范围再开大一点，直接1~n枚举判断可能超时qwq）
2.每次对于可以涂的矩形，颜色相同的直接标记涂上，不同的dfs（而不用全都dfs）
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans;
int x[17],y[17],xx[17],yy[17],c[17],pre[17][17];
bool vis[17];
inline bool chk(int i) {//检查上方的矩形是否都涂过
for (int j=1; j<=pre[i][0]; j++)
if (!vis[pre[i][j]])
return false;
return true;
}
inline void dfs(int step,int num,int co) {//step拿起刷子的最少次数，num涂过的矩形数，co当前颜色
if (step>=ans) return;
for (int i=1; i<=n; i++)//每次把能涂的尽量涂好
if (!vis[i] && chk(i) && c[i]==co)
vis[i]=1,++num;
if (num==n) {
if (ans>step) ans=step;
return;
}
for (register int i=1; i<=n; i++)//寻找颜色不同但可以涂的继续dfs
if (!vis[i] && chk(i)) dfs(step+1,num,c[i]);
}
int main() {
scanf("%d",&n),ans=n;
for (int i=1; i<=n; i++)
scanf("%d%d%d%d%d",&y[i],&x[i],&yy[i],&xx[i],&c[i]);
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if (i^j && yy[i]==y[j])//如果两块矩形不是同一个，且上下贴合
if (x[i]<=x[j] && xx[i]>=xx[j]) {
pre[j][pre[j][0]=1]=i;
break;//如果上矩形覆盖了下矩形的整条边
} else if ((x[i]<=xx[j] && x[i]>=x[j]) || (xx[i]<=xx[j] && xx[i]>=x[j]))//如果覆盖了一部分
pre[j][++pre[j][0]]=i;
for (register int a=1; a<=n ;a++)
if (!pre[a][0]) memset(vis,0,sizeof vis),vis[a]=1,dfs(1,1,c[a]);//每次寻找可以涂的开始dfs
printf("%d",ans);
}