题意 ： 看了好长时间终于看懂题目了，将一个大矩形划分成若干小矩形，告诉你每个小矩形的左上角那个点和右下角那个点的坐标，告诉你这个小矩形要涂的颜色，每个颜色对应一个刷子，问你最少要使用几次刷子。因为你要刷一个矩形之前，必须把这个矩形上方与之直接相邻的所有矩形先刷掉才能刷这个，如果你先用了红色的刷子，然后又用了蓝色的刷子，最后又用了红色的刷子，这算是3次使用而不是两次，样例中，用红色刷B所以D也可以刷了，用蓝色先刷A，然后可以刷C，因为B刷了所以E也可以刷了，最后换刷子把剩下的刷掉，总共三次。
思路 ： 这个题可以用DFS也可以用状压DP，我用的DFS，因为没压出来，，，，，，，这里有分析，链接1，链接2。先将每个矩形看成一个点，然后如果存在上下关系的话，下边那个点的入度+1，先找入度为0的点开始染色，如果这个点已经染掉了的话，那它下边的点入度要减1.。。。。。。。
//
#include <stdio.h>
#include <string.h>
#include <iostream> using namespace std ; struct rectangle
{
int lx,ly ;
int rx,ry ;
int R ;
} rec[];
int degree[] ;
bool mapp[][],vis[] ;
int M ,n;
int cnt ; void build()
{
memset(mapp,false,sizeof(mapp)) ;
memset(degree,,sizeof(degree)) ;
memset(vis,false,sizeof(vis)) ;
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
if(i == j) continue ;
else
{
if(rec[i].ly == rec[j].ry && !(rec[i].rx < rec[j].lx || rec[j].rx < rec[i].lx))
{
mapp[i][j] = true ;
degree[i] ++ ;
}
}
}
}
} void DFS(int r,int ans,int step)
{
if(ans > cnt) return ;
if(step == n)
{
cnt = ans ;
return ;
}
for(int i = ; i < n ; i++)
{
if(!vis[i] && degree[i] == )
{
vis[i] = true ;
for(int j = ; j < n ; j++)
if(mapp[j][i])
degree[j] -- ;
if(rec[i].R == r ) DFS(r,ans,step+) ;
else DFS(rec[i].R,ans + ,step+) ;
vis[i] = false ;
for (int j = ; j < n; j++)
{
if (mapp[j][i]) degree[j]++;
}
}
}
}
int main()
{
scanf("%d",&M) ;
while(M--)
{
scanf("%d",&n) ;
for(int i = ; i < n ; i++)
scanf("%d %d %d %d %d",&rec[i].ly,&rec[i].lx,&rec[i].ry,&rec[i].rx,&rec[i].R) ;
build() ;
cnt = ;
DFS(,,) ;
printf("%d\n",cnt) ;
}
return ;
}