UVa 11038 How many 0's?

題目連結
想法：
　　將問題簡化為求1~m 0的總數，以及1~n 0的總數，然後最後再相減。
　　求1~n 0的總數，要將n分別算每個位數0的個數，舉例如30324：

• 先從右邊第一位'4'開始，其左邊為3032，表示1~30320在"第一位"總共有3032*1=3032個0
• 換第二位數'2'，其左邊為303，表示總共有303*10(右邊有1位)=3030個0
• 再換第三位數也是一樣，30*100=3000個0，
• 注意第四位數為'0'，因此原本應該是3*1000，但第3個1000其實只到324而以，所以為2*1000+324+1=2325個0 (+1是因為別忘了0~324是325個)
• 最後一位'3'，它是最高位數，因此不會有0
• 所以總共為3032+3030+3000+2325=11387

因此，此演算法從最低位(i==1)開始到最高位(i==k)結束，如果第i位不為0，直接左邊數字x10^(i-1)，如果第i位為0，那麼(左邊數字-1)x10^(i-1)+右邊數字+1，最後把每位數的0總數加起來即可。

UVa 620 Cellular Structure

題意：給定O為一條細胞序列

• 若O僅僅為'A'，那麼是simple
• 若O為'OAB'的型態，則OAB的O需要符合O的3種型態的其中一種，如果符合則為Fully-Grown，否則為Mutant。
• 若O為'BOA'的型態，則BOA的O需要符合O的3種型態的其中一種，如果符合則為Mutagenic，否則為Mutant。

想法：

　　用遞迴式parsing來分析O為哪種型態，如果為第2種和第3種，則要繼續呼叫遞迴分析O的型態，只要分析過程中只要O不符合3種的其中一種，則不用再分析，直接回傳Mutant。

UVa 10101 Bangla Numbers

想法：
　　透過遞迴求出答案。

UVa 10696 f91

想法：
　　典型的DP題目，把需要遞迴計算的答案用陣列存起來即可。

UVa 136 & POJ 1338 Ugly Number

想法：
　　下一個數必定是從之前的某個數x2或x3或x5而來的，因此要找第n個數(N[n])，就把前n-1個數x2,x3,x5，找出大於(N[n-1])的最小值。
　　另外找第n個數的時候，乘以2不用每次都從第0個開始乘，每次紀錄2乘到哪個位置，以後就從這個位置往後找即可。例如12是從6這個數字乘以2而來，那麼要找12以後的number的時候，只要從6以後的數字乘以2開始找，因為6以前的數字乘以2不可能大於12，乘以3和乘以5也是同樣道理。

UVa 495 Fibonacci Freeze

想法：
　　本題單純求費柏那西數列，因為n值很大，所以要做大數加法，可以以1000為一個位數，提升效率。

UVa 10446 The Marriage Interview

本題連結
想法：
　　依照題意，將算過的答案記錄下來，在遞迴裡面如果已經算過，就直接回傳答案，避免重複計算。

UVa 10334 Ray Through Glasses

本題連結

想法：
 　　觀察圖，能造成下次數量變多的折線，其最右邊"尖點"都位在上面那條線或下面那條線，例如a2=3，有'2'個"尖點"位在上面那條線，因此能使得a3比a2多出'2'條摺線(a3=a2+2=5)，在觀察a3，有'3'個尖點，因此能使a4比a3多出3個折線(a4=a3+3=8)。那麼尖點的產生方式在於前一個的折線數量，例如a2的尖點來自於a1的箭頭與上面那條線的交點，所以a2尖點的數量=a1，因此我們可得a3=a2+(a2尖點)=a2+a1。
　　簡而言之，本題為費伯那西數列，a(n)=a(n-1)+a(n-2)，而另外由於n可到1000，因此要自己寫大數加法。

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。

UVa 10285 Longest Run on a Snowboard

本題連結
題意：
　　本題給予一個區域內的每個點的高度，滑雪只能由高的點往低的點滑，要求出在這個區域內最多能滑幾個點(滑最遠的方式)。

想法：
　　用一一枚舉的方式，也就是每個點都走走看。
我們定義遞迴式int find_longest (i,j,length) 是回傳area[i][j]這個點所能走的最遠長度。把所有點都算出其最遠長度，在從所有點中選出最大值輸出。