| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛

```#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <cassert>

unsigned long long bar( const std::vector<unsigned>& buf )
{
unsigned long long cnt = 0;
for( unsigned r=0; r!=buf.size(); ++r )
{
for( unsigned c=0; c!=buf[r]; ++c )
{
for( unsigned i=r; i!=buf.size(); ++i )
{
if( buf[i] > c )
cnt += buf[i]-c;
else
break;
}
}
}
return cnt;
}

unsigned long long foo( unsigned n )
{
std::cout << "------ 棍子有 " << n << " 根 ------\n";
if( n < 4 )
return {};

auto next = []( std::vector<unsigned>& buf, unsigned& rem )
{
for( size_t i=buf.size(); i!=0; --i )
{
if( buf[i-1] > 1 )
{
unsigned a = buf[i-1] - 1; // 第 i-1 行有 a 个格子

unsigned rem_new = rem + (i==1)+2; // 剩余的格子数
for( size_t j=i; j!=buf.size(); ++j )
rem_new += buf[j]*2 + 1;

unsigned b = rem_new/(2*a+1); // 能组成几组 a个格子
rem_new %= 2*a+1;
unsigned c = 0; // 最后一行的格子数
if( rem_new > 2 )
{
c = (rem_new-1)/2;
rem_new = (rem_new-1)%2;
}

if( i+b+(c!=0) <= buf[0] )
{
rem = rem_new;
--buf[i-1];
buf.resize( i );
buf.insert( buf.end(), b, a );
if( c != 0 )
buf.push_back( c );

return true;
}
}
}
return false;
};

std::vector<unsigned> max_buf;
unsigned long long max_cnt = 0;

std::vector<unsigned> buf{ (n-1)/3 };
unsigned rem = (n-1)%3;

for( bool b=true; b; b=next(buf,rem) )
{
unsigned long long cnt = bar( buf );
if( cnt > max_cnt )
{
max_cnt = cnt;
max_buf = buf;
}

std::cout << "格{ ";
std::copy( buf.begin(), buf.end(), std::ostream_iterator<unsigned>(std::cout," ") );
std::cout << "} 棍余" << rem << " --- " << cnt << "矩形\n";
}

{
std::cout << "====== 格{ ";
std::copy( max_buf.begin(), max_buf.end(), std::ostream_iterator<unsigned>(std::cout," ") );
std::cout << "} " << max_cnt << "矩形 ======\n\n";
}
return max_cnt;
}

int main( void )
{
for( unsigned n=4; n<=31; ++n )
foo( n );
}
```

------ 棍子有 4 根 ------

====== 格{ 1 } 1矩形 ======

------ 棍子有 5 根 ------

====== 格{ 1 } 1矩形 ======

------ 棍子有 6 根 ------

====== 格{ 1 } 1矩形 ======

------ 棍子有 7 根 ------

====== 格{ 2 } 3矩形 ======

------ 棍子有 8 根 ------

====== 格{ 2 } 3矩形 ======

------ 棍子有 9 根 ------

====== 格{ 2 } 3矩形 ======

------ 棍子有 10 根 ------

====== 格{ 3 } 6矩形 ======

------ 棍子有 11 根 ------

====== 格{ 3 } 6矩形 ======

------ 棍子有 12 根 ------

====== 格{ 2 2 } 9矩形 ======

------ 棍子有 13 根 ------

====== 格{ 4 } 10矩形 ======

------ 棍子有 14 根 ------

====== 格{ 4 } 10矩形 ======

------ 棍子有 15 根 ------

====== 格{ 3 2 } 12矩形 ======

------ 棍子有 16 根 ------

====== 格{ 5 } 15矩形 ======

------ 棍子有 17 根 ------

====== 格{ 3 3 } 18矩形 ======

------ 棍子有 18 根 ------

====== 格{ 3 3 } 18矩形 ======

------ 棍子有 19 根 ------

====== 格{ 6 } 21矩形 ======

------ 棍子有 20 根 ------

====== 格{ 4 3 } 22矩形 ======

------ 棍子有 21 根 ------

====== 格{ 4 3 } 22矩形 ======

------ 棍子有 22 根 ------

====== 格{ 4 4 } 30矩形 ======

------ 棍子有 23 根 ------

====== 格{ 4 4 } 30矩形 ======

------ 棍子有 24 根 ------

====== 格{ 3 3 3 } 36矩形 ======

------ 棍子有 25 根 ------

====== 格{ 8 } 36矩形 ======

------ 棍子有 26 根 ------

====== 格{ 8 } 36矩形 ======

------ 棍子有 27 根 ------

====== 格{ 5 5 } 45矩形 ======

------ 棍子有 28 根 ------

====== 格{ 9 } 45矩形 ======

------ 棍子有 29 根 ------

====== 格{ 4 4 3 } 48矩形 ======

------ 棍子有 30 根 ------

====== 格{ 6 5 } 51矩形 ======

------ 棍子有 31 根 ------

====== 格{ 4 4 4 } 60矩形 ======

[此贴子已经被作者于2024-6-24 21:05编辑过]

```4====== 格{ 1 } 1矩形 ======
5====== 格{ 1 } 1矩形 ======
6====== 格{ 1 } 1矩形 ======
7====== 格{ 2 } 3矩形 ======
8====== 格{ 2 } 3矩形 ======
9====== 格{ 2 } 3矩形 ======
10====== 格{ 3 } 6矩形 ======
11====== 格{ 3 } 6矩形 ======
12====== 格{ 2 2 } 9矩形 ======
13====== 格{ 4 } 10矩形 ======
14====== 格{ 4 } 10矩形 ======
15====== 格{ 3 2 } 12矩形 ======
16====== 格{ 5 } 15矩形 ======
17====== 格{ 3 3 } 18矩形 ======
18====== 格{ 3 3 } 18矩形 ======
19====== 格{ 6 } 21矩形 ======
20====== 格{ 4 3 } 22矩形 ======
21====== 格{ 4 3 } 22矩形 ======
22====== 格{ 4 4 } 30矩形 ======
23====== 格{ 4 4 } 30矩形 ======
24====== 格{ 3 3 3 } 36矩形 ======
25====== 格{ 8 } 36矩形 ======
26====== 格{ 8 } 36矩形 ======
27====== 格{ 5 5 } 45矩形 ======
28====== 格{ 9 } 45矩形 ======
29====== 格{ 4 4 3 } 48矩形 ======
30====== 格{ 6 5 } 51矩形 ======
31====== 格{ 4 4 4 } 60矩形 ======
32====== 格{ 6 6 } 63矩形 ======
33====== 格{ 6 6 } 63矩形 ======
34====== 格{ 11 } 66矩形 ======
35====== 格{ 7 6 } 70矩形 ======
36====== 格{ 5 5 4 } 75矩形 ======
37====== 格{ 7 7 } 84矩形 ======
38====== 格{ 5 5 5 } 90矩形 ======
39====== 格{ 5 5 5 } 90矩形 ======
40====== 格{ 4 4 4 4 } 100矩形 ======
41====== 格{ 4 4 4 4 } 100矩形 ======
42====== 格{ 8 8 } 108矩形 ======
43====== 格{ 8 8 } 108矩形 ======
44====== 格{ 8 8 } 108矩形 ======
45====== 格{ 6 6 6 } 126矩形 ======
46====== 格{ 6 6 6 } 126矩形 ======
47====== 格{ 9 9 } 135矩形 ======
48====== 格{ 9 9 } 135矩形 ======
49====== 格{ 5 5 5 5 } 150矩形 ======
50====== 格{ 5 5 5 5 } 150矩形 ======
51====== 格{ 5 5 5 5 } 150矩形 ======
52====== 格{ 7 7 7 } 168矩形 ======
53====== 格{ 7 7 7 } 168矩形 ======
54====== 格{ 7 7 7 } 168矩形 ======
55====== 格{ 11 10 } 176矩形 ======
56====== 格{ 6 6 6 5 } 186矩形 ======
57====== 格{ 11 11 } 198矩形 ======
58====== 格{ 6 6 6 6 } 210矩形 ======
59====== 格{ 8 8 8 } 216矩形 ======
60====== 格{ 5 5 5 5 5 } 225矩形 ======
61====== 格{ 5 5 5 5 5 } 225矩形 ======
62====== 格{ 12 12 } 234矩形 ======
63====== 格{ 12 12 } 234矩形 ======
64====== 格{ 9 9 8 } 243矩形 ======
65====== 格{ 7 7 7 6 } 252矩形 ======
66====== 格{ 9 9 9 } 270矩形 ======
67====== 格{ 7 7 7 7 } 280矩形 ======
68====== 格{ 7 7 7 7 } 280矩形 ======
69====== 格{ 6 6 6 6 5 } 285矩形 ======
70====== 格{ 8 7 7 7 } 288矩形 ======
71====== 格{ 6 6 6 6 6 } 315矩形 ======
72====== 格{ 14 14 } 315矩形 ======
73====== 格{ 10 10 10 } 330矩形 ======
74====== 格{ 10 10 10 } 330矩形 ======
75====== 格{ 15 14 } 330矩形 ======
76====== 格{ 8 8 8 8 } 360矩形 ======
77====== 格{ 15 15 } 360矩形 ======
78====== 格{ 11 11 10 } 363矩形 ======
79====== 格{ 9 8 8 8 } 369矩形 ======
80====== 格{ 11 11 11 } 396矩形 ======
81====== 格{ 11 11 11 } 396矩形 ======
82====== 格{ 7 7 7 7 7 } 420矩形 ======
83====== 格{ 7 7 7 7 7 } 420矩形 ======
84====== 格{ 6 6 6 6 6 6 } 441矩形 ======
85====== 格{ 9 9 9 9 } 450矩形 ======
86====== 格{ 9 9 9 9 } 450矩形 ======
87====== 格{ 12 12 12 } 468矩形 ======
88====== 格{ 12 12 12 } 468矩形 ======
89====== 格{ 12 12 12 } 468矩形 ======
90====== 格{ 13 12 12 } 481矩形 ======
91====== 格{ 8 8 8 8 7 } 500矩形 ======
92====== 格{ 18 18 } 513矩形 ======
93====== 格{ 8 8 8 8 8 } 540矩形 ======
94====== 格{ 10 10 10 10 } 550矩形 ======
95====== 格{ 10 10 10 10 } 550矩形 ======
96====== 格{ 10 10 10 10 } 550矩形 ======
97====== 格{ 7 7 7 7 7 7 } 588矩形 ======
98====== 格{ 7 7 7 7 7 7 } 588矩形 ======
99====== 格{ 14 14 13 } 588矩形 ======
100====== 格{ 8 7 7 7 7 7 } 596矩形 ======
101====== 格{ 14 14 14 } 630矩形 ======
102====== 格{ 20 20 } 630矩形 ======
103====== 格{ 11 11 11 11 } 660矩形 ======
104====== 格{ 9 9 9 9 9 } 675矩形 ======
105====== 格{ 9 9 9 9 9 } 675矩形 ======
106====== 格{ 15 15 14 } 675矩形 ======
107====== 格{ 21 21 } 693矩形 ======
108====== 格{ 15 15 15 } 720矩形 ======
109====== 格{ 15 15 15 } 720矩形 ======
110====== 格{ 8 8 8 8 8 8 } 756矩形 ======
111====== 格{ 8 8 8 8 8 8 } 756矩形 ======
112====== 格{ 7 7 7 7 7 7 7 } 784矩形 ======
113====== 格{ 7 7 7 7 7 7 7 } 784矩形 ======
114====== 格{ 7 7 7 7 7 7 7 } 784矩形 ======
115====== 格{ 10 10 10 10 10 } 825矩形 ======
116====== 格{ 10 10 10 10 10 } 825矩形 ======
117====== 格{ 23 23 } 828矩形 ======
118====== 格{ 11 10 10 10 10 } 836矩形 ======
119====== 格{ 13 13 13 12 } 858矩形 ======
120====== 格{ 17 17 16 } 867矩形 ======
121====== 格{ 13 13 13 13 } 910矩形 ======
122====== 格{ 17 17 17 } 918矩形 ======
123====== 格{ 9 9 9 9 9 9 } 945矩形 ======
124====== 格{ 9 9 9 9 9 9 } 945矩形 ======
125====== 格{ 8 8 8 8 8 8 7 } 952矩形 ======
126====== 格{ 11 11 11 11 11 } 990矩形 ======
127====== 格{ 8 8 8 8 8 8 8 } 1008矩形 ======
128====== 格{ 8 8 8 8 8 8 8 } 1008矩形 ======
129====== 格{ 18 18 18 } 1026矩形 ======
130====== 格{ 14 14 14 14 } 1050矩形 ======
131====== 格{ 14 14 14 14 } 1050矩形 ======
132====== 格{ 26 26 } 1053矩形 ======
133====== 格{ 15 14 14 14 } 1065矩形 ======
134====== 格{ 10 10 10 10 10 9 } 1095矩形 ======
135====== 格{ 12 12 12 12 11 } 1110矩形 ======
136====== 格{ 10 10 10 10 10 10 } 1155矩形 ======
137====== 格{ 12 12 12 12 12 } 1170矩形 ======
138====== 格{ 12 12 12 12 12 } 1170矩形 ======
139====== 格{ 15 15 15 15 } 1200矩形 ======
140====== 格{ 15 15 15 15 } 1200矩形 ======
141====== 格{ 20 20 19 } 1200矩形 ======
142====== 格{ 9 9 9 9 9 9 9 } 1260矩形 ======
143====== 格{ 20 20 20 } 1260矩形 ======
144====== 格{ 8 8 8 8 8 8 8 8 } 1296矩形 ======
145====== 格{ 8 8 8 8 8 8 8 8 } 1296矩形 ======
146====== 格{ 13 13 13 13 12 } 1300矩形 ======
147====== 格{ 11 11 11 11 11 10 } 1320矩形 ======
148====== 格{ 13 13 13 13 13 } 1365矩形 ======
149====== 格{ 11 11 11 11 11 11 } 1386矩形 ======
150====== 格{ 21 21 21 } 1386矩形 ======
151====== 格{ 21 21 21 } 1386矩形 ======
152====== 格{ 12 11 11 11 11 11 } 1398矩形 ======
153====== 格{ 17 17 16 16 } 1411矩形 ======
154====== 格{ 12 12 11 11 11 11 } 1422矩形 ======
155====== 格{ 10 10 10 10 10 10 9 } 1470矩形 ======
156====== 格{ 10 10 10 10 10 10 9 } 1470矩形 ======
157====== 格{ 10 10 10 10 10 10 10 } 1540矩形 ======
158====== 格{ 10 10 10 10 10 10 10 } 1540矩形 ======
159====== 格{ 14 14 14 14 14 } 1575矩形 ======
160====== 格{ 14 14 14 14 14 } 1575矩形 ======
161====== 格{ 9 9 9 9 9 9 9 9 } 1620矩形 ======
162====== 格{ 12 12 12 12 12 12 } 1638矩形 ======
163====== 格{ 12 12 12 12 12 12 } 1638矩形 ======
164====== 格{ 23 23 23 } 1656矩形 ======
165====== 格{ 23 23 23 } 1656矩形 ======
166====== 格{ 18 18 18 18 } 1710矩形 ======
167====== 格{ 18 18 18 18 } 1710矩形 ======
168====== 格{ 15 15 15 15 14 } 1725矩形 ======
169====== 格{ 19 18 18 18 } 1729矩形 ======
170====== 格{ 15 15 15 15 15 } 1800矩形 ======
171====== 格{ 24 24 24 } 1800矩形 ======
172====== 格{ 11 11 11 11 11 11 11 } 1848矩形 ======
173====== 格{ 11 11 11 11 11 11 11 } 1848矩形 ======
174====== 格{ 11 11 11 11 11 11 11 } 1848矩形 ======
175====== 格{ 13 13 13 13 13 13 } 1911矩形 ======
176====== 格{ 13 13 13 13 13 13 } 1911矩形 ======
177====== 格{ 13 13 13 13 13 13 } 1911矩形 ======
178====== 格{ 10 10 10 10 10 10 10 10 } 1980矩形 ======
179====== 格{ 10 10 10 10 10 10 10 10 } 1980矩形 ======
180====== 格{ 9 9 9 9 9 9 9 9 9 } 2025矩形 ======
181====== 格{ 16 16 16 16 16 } 2040矩形 ======
182====== 格{ 16 16 16 16 16 } 2040矩形 ======
183====== 格{ 16 16 16 16 16 } 2040矩形 ======
184====== 格{ 20 20 20 20 } 2100矩形 ======
185====== 格{ 26 26 26 } 2106矩形 ======
186====== 格{ 14 14 14 14 14 13 } 2121矩形 ======
187====== 格{ 12 12 12 12 12 12 12 } 2184矩形 ======
188====== 格{ 14 14 14 14 14 14 } 2205矩形 ======
189====== 格{ 14 14 14 14 14 14 } 2205矩形 ======
190====== 格{ 17 17 17 17 16 } 2210矩形 ======
191====== 格{ 21 21 21 20 } 2226矩形 ======
192====== 格{ 17 17 17 17 17 } 2295矩形 ======
193====== 格{ 21 21 21 21 } 2310矩形 ======
194====== 格{ 21 21 21 21 } 2310矩形 ======
195====== 格{ 11 11 11 11 11 11 11 11 } 2376矩形 ======
196====== 格{ 11 11 11 11 11 11 11 11 } 2376矩形 ======
197====== 格{ 10 10 10 10 10 10 10 10 9 } 2385矩形 ======
198====== 格{ 12 11 11 11 11 11 11 11 } 2388矩形 ======
199====== 格{ 10 10 10 10 10 10 10 10 10 } 2475矩形 ======
200====== 格{ 10 10 10 10 10 10 10 10 10 } 2475矩形 ======```

[此贴子已经被作者于2024-6-24 21:12编辑过]

```#include <stdio.h>

unsigned foo( unsigned n )
{
if( n < 4 )
return 0;

unsigned max_cnt = 0;
for( unsigned r=1; ; ++r )
{
unsigned c = (n-r)/(1+2*r);
if( r > c )
break;

unsigned rem = n - r - c - 2*r*c;
unsigned h = rem<1 ? 0 : (rem-1)/2;

unsigned cnt = (r*(r+1)/2)*(c*(c+1)/2) + (h*(h+1)/2)*(c+1);
if( max_cnt < cnt )
max_cnt = cnt;
}

return max_cnt;
}

int main( void )
{
unsigned n;
if( 1 != scanf("%u",&n) )
return 1;

printf( "%u\n", foo(n) );
}```

17根组成一个6宫格, 就是18个矩形,  如果再往6宫格里面放一根, 那应该会多好几个矩形出来   -------------错了错了

[此贴子已经被作者于2024-6-26 12:19编辑过]

• 5
• 1/1页
• 1