试用型网站怎么做,wordpress的ico怎么更换,用tornado做网站,建设网站方案 ppt题目描述 CE数码公司开发了一种名为自动涂色机#xff08;APM#xff09;的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。 为了涂色#xff0c;APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子#xff0c;并给所有颜… 题目描述 CE数码公司开发了一种名为自动涂色机APM的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。 为了涂色APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子并给所有颜色为C且符合下面限制的矩形涂色 为了避免颜料渗漏使颜色混合一个矩形只能在所有紧靠它上方的矩形涂色后才能涂色。例如图中矩形F必须在C和D涂色后才能涂色。注意每一个矩形必须立刻涂满不能只涂一部分。 写一个程序求一个使APM拿起刷子次数最少的涂色方案。注意如果一把刷子被拿起超过一次则每一次都必须记入总数中。 输入输出格式 输入格式 第一行为矩形的个数N。下面有N行描述了N个矩形。每个矩形有5个整数描述左上角的y坐标和x坐标右下角的y坐标和x坐标以及预定颜色。 颜色号为1到20的整数。 平板的左上角坐标总是(0, 0)。 坐标的范围是0..99。 N小于16。 输出格式 文件中记录拿起刷子的最少次数。 输入输出样例 输入样例#1 7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2输出样例#1 3 其实这道题就是一道妥妥的深搜但还有一群大佬用DP诶其实我不打DP是因为我根本就不会⊙﹏⊙我们发现这道题有一个坑如果上面没有涂就要先涂上面的。代码 #includebits/stdc.h
using namespace std;
struct str
{int a1,a2,b1,b2,color;
}a[111000];
int b1[11000]{0};//有没有涂
int b[110][110],n,m,ans999;
int b2[11000];//颜色数量
int cmp(str x,str y)//排序
{if(x.a1!y.a1) return x.a1y.a1;//在排横列 return x.a2y.a2;//先排纵列
}
bool cha(int x)
{for(int i0;in;i){if(b[x][i]!b1[i]) return false;//上面没涂,反回false}return true;//反回true
}
void dfs(int x,int ji_lu,int sum)
{if(xans)//如果当前的值大于你要找的值那就不用找了呢O(∩_∩)O~~ {return ;}if(sumn)//涂完了{ansx;return ;}for(int i0;im;i)//枚举每一种颜色 {int h0;if(b2[i]i!ji_lu)//可以涂有颜色涂没有被涂过 {for(int j0;jn;j){//cha函数判断上面有没有被涂颜色 if(!b1[j]a[j].coloricha(j))//如果没涂过且能涂 {b1[j]1;//记录 h;}else if(b1[j]a[j].colori) b1[j];}if(h0)//如果被涂了 {dfs(x1,i,sumh);//进行下一步 }for(int jn-1;j0;j--)//回溯不能上色 {if(b1[j]1a[j].coloricha(j)){b1[j]0;h--;}else if(b1[j]1a[j].colori){b1[j]--;}}}}
}
int main()
{cinn;for(int i0;in;i){cina[i].a1a[i].a2a[i].b1a[i].b2a[i].color;b2[a[i].color];//颜色的数量 }m19;//从零开始 sort(a,an,cmp);//应为蒟蒻不会拓扑排序所以先排一下 for(int i1;in;i){for(int ji-1;j0;j--){if(a[i].a1a[j].b1((a[i].a2a[j].a2a[i].a2a[j].b2)||(a[i].b2a[j].a2a[i].b2a[j].b2))){b[i][j]1;//如果i块的最上面且紧邻j块最下面并且两砖横坐标有重叠部分即i块为j块紧邻的那块砖}}}dfs(0,0,0);coutans;
}做完之后我只想去出题人面前说一句话午时已到。 转载于:https://www.cnblogs.com/dai-jia-ye/p/9323687.html
