题目链接（洛谷的）:https://www.luogu.org/problem/P1283
写这道水题（？）题解的原因有两个：一是因为它花了我几天的空闲时间来解，二是为了提醒自己今后做题一定要先看数据范围。
做这题的时候情绪是这样变化的：
（初见）啊应该是状压没错了吧，数据范围也正好。。
（思索半天后）状压好难写。。改搜索吧。
（第二天）让我重新捋捋昨天我写的这些事什么东西（忘了自己设的变量的含义）
（第三天）想一想怎么剪枝？可以最优性剪枝，可以按颜色种类分类，排序来优化搜索顺序，可以预设一个数组来存当前深度到了哪里。。但是改动的工作量好大啊。
（第四天）盯着颜色号为1到20的整数。平板的左上角坐标总是(0, 0)。坐标的范围是0..99。N小于16（1000ms）思考了半天然后想到——
啊。是不是只要暴力就OK了？
真的诶。。
整洁：枚举每步可能选取的所有block进行dfs。这里的“可能”判断条件：枚举所有已选block，看能不能覆盖当前选中的block的上面。
上代
：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int n; int ans=1e9; bool pinked[20]; struct block{ int u;//upside int d;//down int l;//left int r;//right int c;//color }a[20]; bool check(int j){ for(int i=1;i<=n;i++) { if(!pinked[i]&&a[i].d==a[j].u&&((a[i].r>a[j].l&&a[i].l<=a[j].l)||(a[i].l<a[j].r&&a[i].r>=a[j].r)))return false;//在它上面挡着却没被选的 } return true; } void solve(int cost,int done,int co){ if(cost>ans)return; if(done==n){ ans=cost; return; } for(int i=1; i<=n; i++) { if( !pinked[i]&&check(i) ) { pinked[i]=1; if(a[i].c==co)solve(cost,done+1,co); else solve(cost+1,done+1,a[i].c); pinked[i]=0; } } } int main(){ cin>>n; for(int i=1; i<=n; i++) scanf("%d%d%d%d%d",&a[i].u,&a[i].l,&a[i].d,&a[i].r,&a[i].c); for(int i=1; i<=n; i++) { if(a[i].u==0) { pinked[i]=1; solve(1,1,a[i].c); pinked[i]=0; } } cout<<ans; }
历史（错误）版本就不放了，就这个亚子⑧
原文：https://www.cnblogs.com/snowysniper/p/11379713.html