網頁

2014年1月28日 星期二

UVa 900 Brick Wall Pattern

本題連結

想法:
  我們用-表示橫的磚塊,∣表示直的磚塊,而兩個直的∣∣可以換成兩個橫的=,以長度為5舉例,一開始我們可以先假設都是直的∣∣∣∣∣,首先我們可以將兩塊直的換成橫的=,注意現在兩塊橫的有2個空位,分別是左邊和右邊,然後我們剩下3個直的磚塊,因此把這3個直的放到2個空位的方式為H(2,3)=4。再將兩個直的換成兩塊橫的,變成==,現在4塊橫的有3個空位,然後剩下1個直的,因此為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。