鱼C论坛

 找回密码
 立即注册
查看: 2267|回复: 2

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

[复制链接]
发表于 2016-8-21 01:18:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
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 值。

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-6-6 21:24:41 | 显示全部楼层
records = [[0]*1000 for i in range(1000)]
def F(m,n=3):
    global records
    solutions = 1
    if n>m: return solutions
    if records[n][m] != 0: return records[n][m]
    for i in range(m-n+1):
        for j in range(n,m-i+1):
            solutions += F(m-i-j-1, n)
    records[n][m] = solutions
    return solutions

for n in range(50,500):
    if F(n, 50) > 1000000:
        print(n)
        break
168
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-2-10 21:02:56 | 显示全部楼层
本帖最后由 guosl 于 2022-2-10 21:06 编辑
/*
答案:168
*/
#include <iostream>
#include <vector>
using namespace std;

const int m = 50;
vector<long long> v[2];//意义见114题

int main(void)
{
  v[0].resize(m);
  v[1].resize(m);
  for (int i = 0; i < m; ++i)
  {
    v[0][i] = 1;
    v[1][i] = 0;
  }
  int k = m;
  while (true)
  {
    v[0].push_back(0);
    v[1].push_back(0);
    v[0][k] = v[0][k - 1] + v[1][k - 1];
    for (int i = m; i <= k; ++i)
      v[1][k] += v[0][k - i];
    if (v[0][k] + v[1][k] > 1000000)
    {
      cout << k << endl;
      break;
    }
    ++k;
  }
  return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 21:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表