题目115：找到一种一般化的方法来计算用相分割的木板填充行的方式数量

欧拉计划

Counting block combinations II

NOTE: 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 值。

jerryxjr1220

1. records = [[0]*1000 for i in range(1000)]
   
2. def F(m,n=3):
   
3.     global records
   
4.     solutions = 1
   
5.     if n>m: return solutions
   
6.     if records[n][m] != 0: return records[n][m]
   
7.     for i in range(m-n+1):
   
8.         for j in range(n,m-i+1):
   
9.             solutions += F(m-i-j-1, n)
   
10.     records[n][m] = solutions
    
11.     return solutions
    
12. 
    
13. for n in range(50,500):
    
14.     if F(n, 50) > 1000000:
    
15.         print(n)
    
16.         break

复制代码

168

guosl

1. /*
   
2. 答案：168
   
3. */
   
4. #include <iostream>
   
5. #include <vector>
   
6. using namespace std;
   
7. 
   
8. const int m = 50;
   
9. vector<long long> v[2];//意义见114题
   
10. 
    
11. int main(void)
    
12. {
    
13.   v[0].resize(m);
    
14.   v[1].resize(m);
    
15.   for (int i = 0; i < m; ++i)
    
16.   {
    
17.     v[0][i] = 1;
    
18.     v[1][i] = 0;
    
19.   }
    
20.   int k = m;
    
21.   while (true)
    
22.   {
    
23.     v[0].push_back(0);
    
24.     v[1].push_back(0);
    
25.     v[0][k] = v[0][k - 1] + v[1][k - 1];
    
26.     for (int i = m; i <= k; ++i)
    
27.       v[1][k] += v[0][k - i];
    
28.     if (v[0][k] + v[1][k] > 1000000)
    
29.     {
    
30.       cout << k << endl;
    
31.       break;
    
32.     }
    
33.     ++k;
    
34.   }
    
35.   return 0;
    
36. }

复制代码