Toggle navigation
点码成金编程
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
Home
=>
ProblemSet
=> 4.2-42:地盘划分
Problem1686--4.2-42:地盘划分
1686: 4.2-42:地盘划分
Time Limit:
1
Sec
Memory Limit:
128 MB
Submit:
0
Solved:
3
[
Submit
] [
Status
] [ Creator:
][ 参考程序 ]
Description
划分方式是这样的:
监狱是一个给定的矩形,每一个暗势力的势力范围都必须是一个正方形。划分时,最大的暗势力尽可能多地从矩形中划分一块正方形。接下来,第二大的暗势力在剩下的矩形中尽可能多地划分一块正方形......
如下图所示是一个3*4的矩形,可最少划分为4个势力范围。
也就是说,取走一个3*3的正方形后,将问题规模变成3*1,然后变成2*1,最后变成1*1。
规模每缩小一次,正方形的个数加1。
Input
两个正整数m n,空格分隔,分别表示长和宽
Output
一行一个正整数,即正方形个数
Sample Input
Copy
3 4
Sample Output
Copy
4
HINT
1 <= m, n <= 100
Source/Category
算法
递归
DFS