(2022 Nioke Duo School IV) H-Wall Builder II (Thinking)

Title:

Sample input:

41234

Sample output:

40 0 1 180 1 1 21 1 2 20 0 2 1142 1 3 23 1 4 24 1 5 23 0 5 10 1 2 20 0 3 1184 0 5 12 3 3 43 3 4 44 3 5 43 1 5 23 2 5 30 3 2 40 1 3 20 2 3 30 0 4 1

Title: Given n 1*1 rectangles, n-1 1*2 rectangles, n-2 1*3 rectangles, and 1 1*n rectangle, splicing these rectangles into a largeRectangle, find the minimum perimeter of the larger rectangle.

Analysis: I looked at the data range and found that n is less than 200.Due to how we spliced, the area of ​​the rectangle formed at the end must be fixed. There is an obvious reason that In the case of a certain area, the smaller the difference between the length and the width, the smaller the perimeter.The smaller it is, because ab<=((a+b)/2)^2 can be obtained from the mean inequality, and the equal sign is obtained when a=b, so we must start from the square root of the areaEnumerate the length and width, and then judge whether the given multiple small rectangles can be spliced ​​into a w*h rectangle one by one, and write a separate function to judge. For example, if we enumerate the width, then the first one of a rectangle can be formed.The condition is S%w*w==S, and the second is to see if it can be obtained by splicing with small rectangles.So how do we judge whether it can be obtained by splicing with small rectangles?There is a greedy strategy that says We try to choose a large rectangle every time we fill it, why is this necessarily optimal?In fact, if we need a 1*x rectangle now, we can use a 1*x rectangle or multiple smaller rectangles. When we need a smaller rectangle, the 1*x rectangle isThere is no way to separate, but we can fill with small rectangles, and any time a small rectangle can replace a large rectangle, so this greed must be correct.

Finally, we use a vector p[i] to record the width of the small rectangle filled in the i-th row

Here is the code:

#include#include#include#include#include