题目描述
blablabla
样例
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=50;
struct Candy{
int x1,y1;
int x2,y2;
int col;
}pd[N];
vector<int>v[N];
int n,ans=1<<30;
bool st[N];
bool check(int w)//判断是否上边的矩形已经涂色
{
int t=v[w].size();//记录上边有几个矩形
for(int i=0;i<t;i++)
{
if(!st[v[w][i]])
return false;
}
return true;
}
void dfs(int cnt,int sum,int cl)//cnt是涂色的个数,sum是换的次数,cl是上一次的颜色
{
if(cnt==n)
{
ans=min(ans,sum);
return;
}
if(sum>=ans) return;//剪枝,如果没有涂完结果就比答案大了直接剪掉
for(int i=1;i<=n;i++)
{
if(!st[i] && check(i))
{
st[i]=true;
dfs(cnt+1,sum+(cl!=pd[i].col),pd[i].col);//涂色个数+1,颜色变了就+1,记录颜色
st[i]=false;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>pd[i].x1>>pd[i].y1>>pd[i].x2>>pd[i].y2>>pd[i].col;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j && pd[i].x1==pd[j].x2 && pd[i].y2>=pd[j].y1)//判断矩形有无先后顺序
v[i].push_back(j);
}
dfs(0,0,0);
cout<<ans;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla