UVa 900 Brick Wall Pattern

本題連結

想法：
　　我們用－表示橫的磚塊，∣表示直的磚塊，而兩個直的∣∣可以換成兩個橫的＝，以長度為5舉例，一開始我們可以先假設都是直的∣∣∣∣∣，首先我們可以將兩塊直的換成橫的＝，注意現在兩塊橫的有２個空位，分別是左邊和右邊，然後我們剩下3個直的磚塊，因此把這３個直的放到２個空位的方式為Ｈ(2,3)=4。再將兩個直的換成兩塊橫的，變成＝＝，現在４塊橫的有３個空位，然後剩下１個直的，因此為H(3,1)=3，最後全部加起來就是答案了，1+H(2,3)+H(3,1)=8。
　　本題其實寫出排列組合的C函數就完成了，H(m,n)=C(m+n-1,n)，因此可以先去寫UVa 369是C的題目，而注意type要用long long int。

	#include <cstdio>
	using namespace std;
	typedef long long int llt;
	llt H (int m,int n){
	m = (m+n-1);
	if (n > m/2) n = (m-n);
	int M[100],N[100],i,j;
	for (i=0; i<n; i++){
	M[i] = m - i;
	N[i] = i + 1;
	}
	for (i=0; i<n; i++)
	for (j=0; j<n; j++)
	if (N[j]!=1 && M[i]%N[j] == 0){
	M[i] = M[i]/N[j];
	N[j] = 1;
	break;
	}
	llt a=1, b=1;
	for (i=0; i<n; i++) {
	a *= M[i];
	b *= N[i];
	}
	return a/b;
	}
	int main()
	{
	int L;
	llt patterns;
	while (scanf("%d",&L))
	{
	if (!L) break;
	patterns = 1;
	for (int i=1; L-2*i >= 0; i++)
	patterns += H(i+1,L-2*i);
	printf ("%lld\n",patterns);
	}
	return 0;
	}

view raw [UVa] 900 Brick Wall Pattern.cpp hosted with ❤ by GitHub