题目116：考察方块的替换方法的数量

欧拉计划

Red, green or blue tiles

A row of five black square tiles is to have a number of its tiles replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four).

If red tiles are chosen there are exactly seven ways this can be done.

If green tiles are chosen there are three ways.

And if blue tiles are chosen there are two ways.

Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of replacing the black tiles in a row measuring five units in length.

How many different ways can the black tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?

NOTE: This is related to Problem 117.

题目：

五块黑方形（长为 1）排成一行，我们要从几种长方形中选取，来替换掉五块中的若干块，其中，红色的长为 2，绿色的长为 3，蓝的是 4

如果选取红色的长方形，则正好有七种替换的方式，如下

如果选取绿色的长方形，则有三种

               
蓝色的话，就只有两种方法了

               
       
如果颜色不混搭的话，有 7 + 3 + 2 = 12 种方法来替换五块一行的黑方块。

请问，如果是五十块一行，那么，总共有多少种方式来替换？条件：颜色不混搭，至少使用一种颜色

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

jerryxjr1220

from math import factorial as f
def solve116(n,r=2,g=3,b=4):
  return sum((f(n-i*c+i)//f(i)//f(n-i*c) for c in (r,g,b) for i in range(1,n//c+1)))
print solve116(50)

20492570929

guosl

//20492570929
#include <iostream>
#include <cstring>
using namespace std;

int main(void)
{
  long long f[2][51];
  int a[3] = { 2,3,4 };
  long long nSum = 0;
  for (int i = 0; i < 3; ++i)
  {
    memset(f, 0, sizeof(f));
    for (int j = 1; j <= a[i]; ++j)
      f[0][j] = 1;
    f[1][a[i]] = 1;
    for (int j = a[i] + 1; j <= 50; ++j)
    {
      f[1][j] = f[0][j - a[i]] + f[1][j - a[i]];
      f[0][j] = f[0][j - 1] + f[1][j - 1];
    }
    nSum += f[0][50] - 1 + f[1][50];
  }
  cout << nSum << endl;
  return 0;
}