程序代码：

#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 );
}

[此贴子已经被作者于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) );
}

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