题目115：找到一种一般化的方法来计算用相分割的木板填充行的方式数量
Counting block combinations IINOTE: This is a more difficult version of Problem 114.
A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.
Let the fill-count function, F(m, n), represent the number of ways that a row can be filled.
For example, F(3, 29) = 673135 and F(3, 30) = 1089155.
That is, for m = 3, it can be seen that n = 30 is the smallest value for which the fill-count function first exceeds one million.
In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds one million.
For m = 50, find the least value of n for which the fill-count function first exceeds one million.
题目：
注意：本题是题目114的一个更难的版本。
一个长度为 n 的行上面放有最小长度为 m 的红色块，要求相邻的两个红色块（长度可不相同）之间至少要用长度为 1 的黑色方块相分割。
用填充数量函数 F(m,n) 来代表按照上述要求能够填充一行的方式的数量。
例如，F(3, 29) = 673135， F(3, 30) = 1089155。
也就是说，对于 m=3，可以看出 n=30 是使得填充数量函数超过一百万的最小的值。
类似的，对于 m=10，可以证明 F(10, 56) = 880711， F(10, 57) = 1148904，所以 n=57 是使得填充数量函数超过一百万的最小的值。
对于 m=50，求使得填充数量函数超过一百万的最小的 n 值。
records = [*1000 for i in range(1000)]
def F(m,n=3):
global records
solutions = 1
if n>m: return solutions
if records != 0: return records
for i in range(m-n+1):
for j in range(n,m-i+1):
solutions += F(m-i-j-1, n)
records = solutions
return solutions
for n in range(50,500):
if F(n, 50) > 1000000:
print(n)
break
168 本帖最后由 guosl 于 2022-2-10 21:06 编辑
/*
答案：168
*/
#include <iostream>
#include <vector>
using namespace std;
const int m = 50;
vector<long long> v;//意义见114题
int main(void)
{
v.resize(m);
v.resize(m);
for (int i = 0; i < m; ++i)
{
v = 1;
v = 0;
}
int k = m;
while (true)
{
v.push_back(0);
v.push_back(0);
v = v + v;
for (int i = m; i <= k; ++i)
v += v;
if (v + v > 1000000)
{
cout << k << endl;
break;
}
++k;
}
return 0;
}
页:
[1]