题目描述
有一个矩形，上面有若干的矩形需要涂某一种颜色，并且一个矩形能涂色当且仅当与它的上边直接相接的矩形都已涂完。求刷子最少要换几次颜色。
思路
看这么小的数据范围想都不用想直接爆搜。我们先预处理出每个矩形涂色之间需要那几个矩形涂色完毕，然后暴力枚举当前涂那个矩形，全部涂完后记录答案。这道题只需要加一个最优性剪枝就可以跑的飞快，判当前换颜色数是否大于ans即可。
代码
#include <bits/stdc++.h> using namespace std; struct aa { int x1,x2,y1,y2; int v; }a[20]; vector<int> p[20]; int n,vis[30],ans; bool check(int x) { for(int i=0;i<p[x].size();i++) if(!vis[p[x][i]])return 0; return 1; } void dfs(int x,int s,int last) { // cout<<x<<' '<<s<<' '<<last<<endl; if(x>=ans)return ; if(s==n) { ans=min(ans,x); return ; } for(int i=1;i<=n;i++) if(!vis[i]&&(check(i)||a[i].y1==0)) { vis[i]=1; dfs(x+(last!=a[i].v),s+1,a[i].v); vis[i]=0; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d%d%d",&a[i].y1,&a[i].x1,&a[i].y2,&a[i].x2,&a[i].v); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&a[i].y2==a[j].y1&&!(a[i].x1>=a[j].x2||a[i].x2<=a[j].x1)) p[j].push_back(i); ans=0x7fffffff; dfs(0,0,0); printf("%d",ans); return 0; }