CF竞赛题目讲解_CF1775F(排列组合 + DP)
2023-01-24 16:52 作者:Clayton_Zhou | 我要投稿
AC代码
https://codeforces.com/contest/1775/submission/190267560
题意:
如你所知,火星科学家正在积极从事太空研究。冥王星是最高优先级之一。
为了更详细地研究这颗行星,决定在冥王星上建造一个实验室。
众所周知,实验室将由n大小相等的方形块组成。为了方便起见,
我们假设冥王星的表面是一个由垂直线和水平线划分成单位正方形的平面。
每个广场要么被一个实验区占用,要么没有,只有n个广场被占用。
因为每个街区都是方形的,所以它有四堵墙。如果一堵墙与另一块相邻,则将其视为内侧,否则视为外侧。
冥王星以其极冷的温度而闻名,因此实验室的外墙必须隔热。每个外墙需要一个保温层。
因此,实验室外墙的总长度(即其周长)越大,就需要更多的隔热材料。
考虑下图中的实验室布局。结果表明,实验室由n=33个区块组成,所有区块共有24个外墙,
即需要24个绝缘单元。你应该以最佳的方式建造实验室,即尽量减少隔热层的数量。
另一方面,可能有许多最佳选择,因此科学家可能会对使用最小数量的绝缘材料(取素数m的模)
建造实验室的方法感兴趣。
如果两种方式在重叠而不转弯时相同,则认为它们是相同的。因此,如果实验室计划被旋转90°,
这样的新计划可以被视为一种单独的方式。
为了帮助科学家探索冥王星,你需要编写一个程序来解决这些难题。
输出:
第一行包含两个整数t和u-测试用例的数量和测试类型。
如果u=1,你需要找到以最佳方式构建实验室的任何方法,
如果u=2,你需要计算所有方案的数量。
题解:
排列组合 + DP