题目117：考察使用不同型号的砖块铺满一行的方法

欧拉计划

Red, green, and blue tiles

Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.

How many ways can a row measuring fifty units in length be tiled?

NOTE: This is related to Problem 116.

题目：

有以下几种长条：红色的 2*1，绿色的 3*1，蓝色的 4*1。

使用黑色方块 1*1 和长条进行组合，想得到 5*1 的矩形，则有 15 种不同的方法：
       

请问，50*1 的矩形有多少种方法可以形成？

注意：该题与题目116有关。

jerryxjr1220

from math import factorial as f
def P(n,m):
    return f(n)//f(m)//f(n-m)
def solve117(n,r=2,g=3,b=4):
    total = 0
    for i in range(n//r+1):
        for j in range(n//g+1):
            for k in range(n//b+1):
                if i*r+j*g+k*b > n: break
                bk = n - i*r - j*g - k*b
                total += P(bk+i+j+k,i)*P(bk+j+k, j)*P(bk+k,k)
    return total
print(solve117(50))

100808458960497

guosl

//100808458960497
#include <iostream>
using namespace std;

long long f[4][51];
int a[4] = { 1,2,3,4 };

int main(void)
{
  f[0][0] = 1;
  for (int i = 1; i <= 50; ++i)
  {
    for (int k = 0; k <= 3; ++k)
    {
      if (i >= a[k])
        f[k][i] = f[0][i - a[k]] + f[1][i - a[k]] + f[2][i - a[k]] + f[3][i - a[k]];
    }
  }
  cout << f[0][50] + f[1][50] + f[2][50] + f[3][50] << endl;
  return 0;
}