|
#2
rjsp2024-06-24 16:44
非常难，我先死算，再找规律（尚未找到）
 程序代码：#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 } 棍余0 --- 1矩形 ====== 格{ 1 } 1矩形 ====== ------ 棍子有 5 根 ------ 格{ 1 } 棍余1 --- 1矩形 ====== 格{ 1 } 1矩形 ====== ------ 棍子有 6 根 ------ 格{ 1 } 棍余2 --- 1矩形 ====== 格{ 1 } 1矩形 ====== ------ 棍子有 7 根 ------ 格{ 2 } 棍余0 --- 3矩形 格{ 1 1 } 棍余0 --- 3矩形 ====== 格{ 2 } 3矩形 ====== ------ 棍子有 8 根 ------ 格{ 2 } 棍余1 --- 3矩形 格{ 1 1 } 棍余1 --- 3矩形 ====== 格{ 2 } 3矩形 ====== ------ 棍子有 9 根 ------ 格{ 2 } 棍余2 --- 3矩形 格{ 1 1 } 棍余2 --- 3矩形 ====== 格{ 2 } 3矩形 ====== ------ 棍子有 10 根 ------ 格{ 3 } 棍余0 --- 6矩形 格{ 2 1 } 棍余0 --- 5矩形 ====== 格{ 3 } 6矩形 ====== ------ 棍子有 11 根 ------ 格{ 3 } 棍余1 --- 6矩形 格{ 2 1 } 棍余1 --- 5矩形 ====== 格{ 3 } 6矩形 ====== ------ 棍子有 12 根 ------ 格{ 3 } 棍余2 --- 6矩形 格{ 2 2 } 棍余0 --- 9矩形 格{ 2 1 } 棍余2 --- 5矩形 ====== 格{ 2 2 } 9矩形 ====== ------ 棍子有 13 根 ------ 格{ 4 } 棍余0 --- 10矩形 格{ 3 1 } 棍余0 --- 8矩形 格{ 2 2 } 棍余1 --- 9矩形 ====== 格{ 4 } 10矩形 ====== ------ 棍子有 14 根 ------ 格{ 4 } 棍余1 --- 10矩形 格{ 3 1 } 棍余1 --- 8矩形 格{ 2 2 } 棍余2 --- 9矩形 ====== 格{ 4 } 10矩形 ====== ------ 棍子有 15 根 ------ 格{ 4 } 棍余2 --- 10矩形 格{ 3 2 } 棍余0 --- 12矩形 格{ 3 1 } 棍余2 --- 8矩形 格{ 2 2 1 } 棍余0 --- 12矩形 ====== 格{ 3 2 } 12矩形 ====== ------ 棍子有 16 根 ------ 格{ 5 } 棍余0 --- 15矩形 格{ 4 1 } 棍余0 --- 12矩形 格{ 3 2 } 棍余1 --- 12矩形 格{ 3 1 1 } 棍余0 --- 11矩形 格{ 2 2 1 } 棍余1 --- 12矩形 ====== 格{ 5 } 15矩形 ====== ------ 棍子有 17 根 ------ 格{ 5 } 棍余1 --- 15矩形 格{ 4 1 } 棍余1 --- 12矩形 格{ 3 3 } 棍余0 --- 18矩形 格{ 3 2 } 棍余2 --- 12矩形 格{ 3 1 1 } 棍余1 --- 11矩形 格{ 2 2 2 } 棍余0 --- 18矩形 ====== 格{ 3 3 } 18矩形 ====== ------ 棍子有 18 根 ------ 格{ 5 } 棍余2 --- 15矩形 格{ 4 2 } 棍余0 --- 16矩形 格{ 4 1 } 棍余2 --- 12矩形 格{ 3 3 } 棍余1 --- 18矩形 格{ 3 2 1 } 棍余0 --- 15矩形 格{ 3 1 1 } 棍余2 --- 11矩形 格{ 2 2 2 } 棍余1 --- 18矩形 ====== 格{ 3 3 } 18矩形 ====== ------ 棍子有 19 根 ------ 格{ 6 } 棍余0 --- 21矩形 格{ 5 1 } 棍余0 --- 17矩形 格{ 4 2 } 棍余1 --- 16矩形 格{ 4 1 1 } 棍余0 --- 15矩形 格{ 3 3 } 棍余2 --- 18矩形 格{ 3 2 1 } 棍余1 --- 15矩形 格{ 2 2 2 } 棍余2 --- 18矩形 ====== 格{ 6 } 21矩形 ====== ------ 棍子有 20 根 ------ 格{ 6 } 棍余1 --- 21矩形 格{ 5 1 } 棍余1 --- 17矩形 格{ 4 3 } 棍余0 --- 22矩形 格{ 4 2 } 棍余2 --- 16矩形 格{ 4 1 1 } 棍余1 --- 15矩形 格{ 3 3 1 } 棍余0 --- 21矩形 格{ 3 2 2 } 棍余0 --- 21矩形 格{ 3 2 1 } 棍余2 --- 15矩形 ====== 格{ 4 3 } 22矩形 ====== ------ 棍子有 21 根 ------ 格{ 6 } 棍余2 --- 21矩形 格{ 5 2 } 棍余0 --- 21矩形 格{ 5 1 } 棍余2 --- 17矩形 格{ 4 3 } 棍余1 --- 22矩形 格{ 4 2 1 } 棍余0 --- 19矩形 格{ 4 1 1 } 棍余2 --- 15矩形 格{ 3 3 1 } 棍余1 --- 21矩形 格{ 3 2 2 } 棍余1 --- 21矩形 ====== 格{ 4 3 } 22矩形 ====== ------ 棍子有 22 根 ------ 格{ 7 } 棍余0 --- 28矩形 格{ 6 1 } 棍余0 --- 23矩形 格{ 5 2 } 棍余1 --- 21矩形 格{ 5 1 1 } 棍余0 --- 20矩形 格{ 4 4 } 棍余0 --- 30矩形 格{ 4 3 } 棍余2 --- 22矩形 格{ 4 2 1 } 棍余1 --- 19矩形 格{ 4 1 1 1 } 棍余0 --- 19矩形 格{ 3 3 2 } 棍余0 --- 27矩形 格{ 3 3 1 } 棍余2 --- 21矩形 格{ 3 2 2 } 棍余2 --- 21矩形 ====== 格{ 4 4 } 30矩形 ====== ------ 棍子有 23 根 ------ 格{ 7 } 棍余1 --- 28矩形 格{ 6 1 } 棍余1 --- 23矩形 格{ 5 3 } 棍余0 --- 27矩形 格{ 5 2 } 棍余2 --- 21矩形 格{ 5 1 1 } 棍余1 --- 20矩形 格{ 4 4 } 棍余1 --- 30矩形 格{ 4 3 1 } 棍余0 --- 25矩形 格{ 4 2 2 } 棍余0 --- 25矩形 格{ 4 2 1 } 棍余2 --- 19矩形 格{ 4 1 1 1 } 棍余1 --- 19矩形 格{ 3 3 2 } 棍余1 --- 27矩��� ====== 格{ 4 4 } 30矩形 ====== ------ 棍子有 24 根 ------ 格{ 7 } 棍余2 --- 28矩形 格{ 6 2 } 棍余0 --- 27矩形 格{ 6 1 } 棍余2 --- 23矩形 格{ 5 3 } 棍余1 --- 27矩形 格{ 5 2 1 } 棍余0 --- 24矩形 格{ 5 1 1 } 棍余2 --- 20矩形 格{ 4 4 } 棍余2 --- 30矩形 格{ 4 3 1 } 棍余1 --- 25矩形 格{ 4 2 2 } 棍余1 --- 25矩形 格{ 4 2 1 1 } 棍余0 --- 23矩形 格{ 4 1 1 1 } 棍余2 --- 19矩形 格{ 3 3 3 } 棍余0 --- 36矩形 格{ 3 3 2 } 棍余2 --- 27矩形 ====== 格{ 3 3 3 } 36矩形 ====== ------ 棍子有 25 根 ------ 格{ 8 } 棍余0 --- 36矩形 格{ 7 1 } 棍余0 --- 30矩形 格{ 6 2 } 棍余1 --- 27矩形 格{ 6 1 1 } 棍余0 --- 26矩形 格{ 5 4 } 棍余0 --- 35矩形 格{ 5 3 } 棍余2 --- 27矩形 格{ 5 2 1 } 棍余1 --- 24矩形 格{ 5 1 1 1 } 棍余0 --- 24矩形 格{ 4 4 1 } 棍余0 --- 33矩形 格{ 4 3 2 } 棍余0 --- 31矩形 格{ 4 3 1 } 棍余2 --- 25矩形 格{ 4 2 2 } 棍余2 --- 25矩形 格{ 4 2 1 1 } 棍余1 --- 23矩形 格{ 3 3 3 } 棍余1 --- 36矩形 ====== 格{ 8 } 36矩形 ====== ------ 棍子有 26 根 ------ 格{ 8 } 棍余1 --- 36矩形 格{ 7 1 } 棍余1 --- 30矩形 格{ 6 3 } 棍余0 --- 33矩形 格{ 6 2 } 棍余2 --- 27矩形 格{ 6 1 1 } 棍余1 --- 26矩形 格{ 5 4 } 棍余1 --- 35矩形 格{ 5 3 1 } 棍余0 --- 30矩形 格{ 5 2 2 } 棍余0 --- 30矩形 格{ 5 2 1 } 棍余2 --- 24矩形 格{ 5 1 1 1 } 棍余1 --- 24矩形 格{ 4 4 1 } 棍余1 --- 33矩形 格{ 4 3 2 } 棍余1 --- 31矩形 格{ 4 3 1 1 } 棍余0 --- 29矩形 格{ 4 2 2 1 } 棍余0 --- 29矩形 格{ 4 2 1 1 } 棍余2 --- 23矩形 格{ 3 3 3 } 棍余2 --- 36矩形 ====== 格{ 8 } 36矩形 ====== ------ 棍子有 27 根 ------ 格{ 8 } 棍余2 --- 36矩形 格{ 7 2 } 棍余0 --- 34矩形 格{ 7 1 } 棍余2 --- 30矩形 格{ 6 3 } 棍余1 --- 33矩形 格{ 6 2 1 } 棍余0 --- 30矩形 格{ 6 1 1 } 棍余2 --- 26矩形 格{ 5 5 } 棍余0 --- 45矩形 格{ 5 4 } 棍余2 --- 35矩形 格{ 5 3 1 } 棍余1 --- 30矩形 格{ 5 2 2 } 棍余1 --- 30矩形 格{ 5 2 1 1 } 棍余0 --- 28矩形 格{ 5 1 1 1 } 棍余2 --- 24矩形 格{ 4 4 2 } 棍余0 --- 39矩形 格{ 4 4 1 } 棍余2 --- 33矩形 格{ 4 3 3 } 棍余0 --- 40矩形 格{ 4 3 2 } 棍余2 --- 31矩形 格{ 4 3 1 1 } 棍余1 --- 29矩形 格{ 4 2 2 1 } 棍余1 --- 29矩形 格{ 3 3 3 1 } 棍余0 --- 40矩形 ====== 格{ 5 5 } 45矩形 ====== ------ 棍子有 28 根 ------ 格{ 9 } 棍余0 --- 45矩形 格{ 8 1 } 棍余0 --- 38矩形 格{ 7 2 } 棍余1 --- 34矩形 格{ 7 1 1 } 棍余0 --- 33矩形 格{ 6 4 } 棍余0 --- 41矩形 格{ 6 3 } 棍余2 --- 33矩形 格{ 6 2 1 } 棍余1 --- 30矩形 格{ 6 1 1 1 } 棍余0 --- 30矩形 格{ 5 5 } 棍余1 --- 45矩形 格{ 5 4 1 } 棍余0 --- 38矩形 格{ 5 3 2 } 棍余0 --- 36矩形 格{ 5 3 1 } 棍余2 --- 30矩形 格{ 5 2 2 } 棍余2 --- 30矩形 格{ 5 2 1 1 } 棍余1 --- 28矩形 格{ 5 1 1 1 1 } 棍余0 --- 29矩形 格{ 4 4 2 } 棍余1 --- 39矩形 格{ 4 4 1 1 } 棍余0 --- 37矩形 格{ 4 3 3 } 棍余1 --- 40矩形 格{ 4 3 2 1 } 棍余0 --- 35矩形 格{ 4 3 1 1 } 棍余2 --- 29矩形 格{ 4 2 2 2 } 棍余0 --- 37矩形 格{ 4 2 2 1 } 棍余2 --- 29矩形 格{ 3 3 3 1 } 棍余1 --- 40矩形 ====== 格{ 9 } 45矩形 ====== ------ 棍子有 29 根 ------ 格{ 9 } 棍余1 --- 45矩形 格{ 8 1 } 棍余1 --- 38矩形 格{ 7 3 } 棍余0 --- 40矩形 格{ 7 2 } 棍余2 --- 34矩形 格{ 7 1 1 } 棍余1 --- 33矩形 格{ 6 4 } 棍余1 --- 41矩形 格{ 6 3 1 } 棍余0 --- 36矩形 格{ 6 2 2 } 棍余0 --- 36矩形 格{ 6 2 1 } 棍余2 --- 30矩形 格{ 6 1 1 1 } 棍余1 --- 30矩形 格{ 5 5 } 棍余2 --- 45矩形 格{ 5 4 1 } 棍余1 --- 38矩形 格{ 5 3 2 } 棍余1 --- 36矩形 格{ 5 3 1 1 } 棍余0 --- 34矩形 格{ 5 2 2 1 } 棍余0 --- 34矩形 格{ 5 2 1 1 } 棍余2 --- 28矩形 格{ 5 1 1 1 1 } 棍余1 --- 29矩形 格{ 4 4 3 } 棍余0 --- 48矩形 格{ 4 4 2 } 棍余2 --- 39矩形 格{ 4 4 1 1 } 棍余1 --- 37矩形 格{ 4 3 3 } 棍余2 --- 40矩形 格{ 4 3 2 1 } 棍余1 --- 35矩形 格{ 4 2 2 2 } 棍余1 --- 37矩形 格{ 3 3 3 2 } 棍余0 --- 48矩形 ====== 格{ 4 4 3 } 48矩形 ====== ------ 棍子有 30 根 ------ 格{ 9 } 棍余2 --- 45矩形 格{ 8 2 } 棍余0 --- 42矩形 格{ 8 1 } 棍余2 --- 38矩形 格{ 7 3 } 棍余1 --- 40矩形 格{ 7 2 1 } 棍余0 --- 37矩形 格{ 7 1 1 } 棍余2 --- 33矩形 格{ 6 5 } 棍余0 --- 51矩形 格{ 6 4 } 棍余2 --- 41矩形 格{ 6 3 1 } 棍余1 --- 36矩形 格{ 6 2 2 } 棍余1 --- 36矩形 格{ 6 2 1 1 } 棍余0 --- 34矩形 格{ 6 1 1 1 } 棍余2 --- 30矩形 格{ 5 5 1 } 棍余0 --- 48矩形 格{ 5 4 2 } 棍余0 --- 44矩形 格{ 5 4 1 } 棍余2 --- 38矩形 格{ 5 3 3 } 棍余0 --- 45矩形 格{ 5 3 2 } 棍余2 --- 36矩形 格{ 5 3 1 1 } 棍余1 --- 34矩形 格{ 5 2 2 1 } 棍余1 --- 34矩形 格{ 5 2 1 1 1 } 棍余0 --- 33矩形 格{ 5 1 1 1 1 } 棍余2 --- 29矩形 格{ 4 4 3 } 棍余1 --- 48矩形 格{ 4 4 2 1 } 棍余0 --- 43矩形 格{ 4 4 1 1 } 棍余2 --- 37矩形 格{ 4 3 3 1 } 棍余0 --- 44矩形 格{ 4 3 2 2 } 棍余0 --- 43矩形 格{ 4 3 2 1 } 棍余2 --- 35矩形 格{ 4 2 2 2 } 棍余2 --- 37矩形 格{ 3 3 3 2 } 棍余1 --- 48矩形 ====== 格{ 6 5 } 51矩形 ====== ------ 棍子有 31 根 ------ 格{ 10 } 棍余0 --- 55矩形 格{ 9 1 } 棍余0 --- 47矩形 格{ 8 2 } 棍余1 --- 42矩形 格{ 8 1 1 } 棍余0 --- 41矩形 格{ 7 4 } 棍余0 --- 48矩形 格{ 7 3 } 棍余2 --- 40矩形 格{ 7 2 1 } 棍余1 --- 37矩形 格{ 7 1 1 1 } 棍余0 --- 37矩形 格{ 6 5 } 棍余1 --- 51矩形 格{ 6 4 1 } 棍余0 --- 44矩形 格{ 6 3 2 } 棍余0 --- 42矩形 格{ 6 3 1 } 棍余2 --- 36矩形 格{ 6 2 2 } 棍余2 --- 36矩形 格{ 6 2 1 1 } 棍余1 --- 34矩形 格{ 6 1 1 1 1 } 棍余0 --- 35矩形 格{ 5 5 1 } 棍余1 --- 48矩形 格{ 5 4 2 } 棍余1 --- 44矩形 格{ 5 4 1 1 } 棍余0 --- 42矩形 格{ 5 3 3 } 棍余1 --- 45矩形 格{ 5 3 2 1 } 棍余0 --- 40矩形 格{ 5 3 1 1 } 棍余2 --- 34矩形 格{ 5 2 2 2 } 棍余0 --- 42矩形 格{ 5 2 2 1 } 棍余2 --- 34矩形 格{ 5 2 1 1 1 } 棍余1 --- 33矩形 格{ 4 4 4 } 棍余0 --- 60矩形 格{ 4 4 3 } 棍余2 --- 48矩形 格{ 4 4 2 1 } 棍余1 --- 43矩形 格{ 4 3 3 1 } 棍余1 --- 44矩形 格{ 4 3 2 2 } 棍余1 --- 43矩形 格{ 3 3 3 3 } 棍余0 --- 60矩形 ====== 格{ 4 4 4 } 60矩形 ====== [此贴子已经被作者于2024-6-24 21:05编辑过] |
有若干根长度相等的木棍，用它们最多可以组成多少个矩形？
程序输入（木棍数量）： 程序输出（矩形个数）：
示例：
输入：17
输出：18
