宝典2第二章划分地盘 - 省实信息学奥赛

问题 2094. -- 宝典2第二章划分地盘

2094: 宝典2第二章划分地盘

时间限制: 1 Sec 内存限制: 128 MB
提交: 26 解决: 12
[上一题][提交][讨论版][状态][下一题][正确][下一题]

题目描述

【题目描述】地盘划分（territory.cpp/c/pas）
修罗王和邪狼被关进监狱，该监狱的地下秩序实际被不少暗势力所把持，这些暗势力根据其实力不同，划分出了大大小小的势力范围。具体划分方式是这样的：监狱是一个给定的矩形，每一个暗势力的势力范围都必须是一个正方形，划分时，最大的暗势力尽可能多地从矩形中划分一块正方形，接下来，第二大的暗势力在剩下的矩形中尽可能多的划分一块正方形……例如，图2.1中所示是一个3×4的矩阵，可最少划分为４个势力范围。
也就是说，取走一个3×3的正方形后，将问题规模变成3×1，然后变成2×1，最后变成1×1。规模每缩小一次，正方形的个数加1。
<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKkAAABuCAYAAABcODMjAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAAJDSURBVHhe7dzBasMwEEXRuP//z20HIhAh3aRW/JQ5B0SLN0bNZRR34eP7122R4zjuv9HFipy+7j8hlkiJ97bjfuFtnqp7v/uewxX3vvpvPay4t0lKPJEST6TEEynxRNpQPejMK51Im6ko6wl8rHEtmUibe/e/q14h0mZ2iPKRSJsbx38ykRJPpI3tMEWLSJvaJdAi0oZ2CrSItJm/Aq3rqUTaUAX5uJInq0ibqRifrWQiJZ5IiSdS4omUeCIlnkiJJ1LiiZR4IiWeSIknUuKJlHgiJZ6X6HKqFTl59eMCV9w7ZSCs2Lfjnngm6QJXT9JPu7dJSjyREk+kxBPp3fy96tPVXueVrn2ku3xQZ6m91sPNWONasvaRzh9WB4973WHvjvvmxmRNJtLGdgi0iLSp8T00/ftoEWlTNUHHFPXgRDTHPZxApM15ut/ETg8R/1V7nJfjfhPjIWKHD+y/5r3usl+REk+kxBMp8URKPJEST6TEEynxREo8kRJPpMQTKfFESjyREs/7STnVipy8VW+BK+6dMhBW7NtxTzyTdIGrJ+mn3dskJZ5IiSdS4om0ufn7ZCqRNrZDoEWkTV3xH4hXiZR4Im1opylaRNrMboEWkTayY6BFpM1UqPOar6USaSM1RR/XfD2VSIknUuKJtLnkY34QKfFESjyREk+kxBMp8URKPJEST6TEEynxREo8kRJPpMQTKfG8n5RTrcjJJCWeSIm39LiHM5ikxBMp8URKPJEST6TEEynxREo8kRJPpIS73X4AFGwPuvE9ABsAAAAASUVORK5CYII=" />
【输入格式】
输入文件为territory.in，两个int整数，即长和宽。
【输出格式】
输出文件为territory.out，即正方形个数。
【输入样例】
３　4
【输出样例】
４

广东实验中学信息学奥赛评测系统

2094: 宝典2第二章划分地盘

题目描述

标签