设置网站解析/惠州百度seo地址

题意：有一个矩形框由n个小的矩形组成，现在要把每个矩形涂上一种给定的颜色c(可相同可不同，如下图)。涂每个小矩阵有一个条件，就是位于它上面，并且与它连接的小矩形必须先涂好。当然满足条件的同一种颜色可以一起涂，问最少需要多少把刷子（每把刷子一种颜色，如果刷子拿起来多次，那么这些都要加上）。原题上有图（http://poj.org/problem?id=1691）

思路：dfs。先遍历每对小矩形，确定他们有没有依赖关系。g数组和d数组的意义见代码。第一次写没加now>res的那个剪枝导致TLE。加上便AC。

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define N 20
struct point{int u,d,l,r;int color;
}p[N];
int used[N],d[N],g[N][N];
int T,n,res;
void dfs(int x,int c,int now){//x是已经给多少个矩形上好色，c表示上一个上色矩形的颜色int i,j;if(now > res)//如果缺少这个剪枝会TLEreturn ;if(x == n){res = min(res, now);return;}for(i = 1;i<=n;i++)if(!d[i] && !used[i]){//d[i]==0表示第i个矩形其上面的矩形都已经上好色used[i] = 1;for(j = 1;j<=n;j++)d[j] -= g[j][i];dfs(x+1,p[i].color , now+ (c==p[i].color?0:1));//如果和上一个上色矩形的颜色相同，那么涂色数量不必加used[i] = 0;for(j = 1;j<=n;j++)d[j] += g[j][i];}
}
int main(){scanf("%d",&T);while(T--){int i,j;res=22;memset(used,0,sizeof(used));memset(g,0,sizeof(g));memset(d, 0, sizeof(d));scanf("%d",&n);for(i = 1;i<=n;i++)scanf("%d %d %d %d %d",&p[i].u,&p[i].l,&p[i].d,&p[i].r,&p[i].color);for(i = 1;i<=n;i++)for(j = 1;j<=n;j++)if(p[i].d == p[j].u && !(p[i].r<=p[j].l || p[i].l>=p[j].r))//第i个矩形在第j个矩形的上面g[j][i] = 1;//表示要给第j个矩形上色，那么第i个矩形必须已经上好颜色for(i = 1;i<=n;i++)for(j = 1;j<=n;j++)d[i] += g[i][j];//d[i]表示第i个矩形依赖的矩形个数dfs(0,0,0);printf("%d\n",res);}return 0;
}