uva 11401 - Triangle Counting

題目出處：Uva

題目連結：11401 - Triangle Counting

題目大意：link(luckycat)

解題方法：透過dynamic programming的方法，若要討論使用1~N的邊，則會是使用1~N-1的情況加上有使用N的情況(當然此時，N會是最大邊)。
以N = 10為例子。三條邊可以為（由左至右是由小到大）：
邊a 邊b 邊c 幾種組合
2~8  9  10      7
3~7  8  10      5
4~6  7  10      3
5~5  6  10      1
因此，以邊長10為最大邊的情況，可以透過等差級數(S)去計算。 
S = a1 + (a1+d) + (a1+2*d) + ... + (a1+(n-1)*d)
= a1*n + ((n-1)+0)*(n)/2*d
= a1*n + (n-1)*n/2*(-2)
= a1*n - (n-1)*n
= n*(a1-n+1)
a1是首項(N-3)，d是公差(-2)，n是數量((a1+1)/2)。
因此，dp[i] = dp[i-1] + S

注　　意：需要化簡，過程中才不會overflow。

代碼如下：

uva 11384 - Help is needed for Dexter

題目出處：Uva

題目連結：11384 - Help is needed for Dexter

題目大意：link(luckycat)

解題方法：這題滿有趣的，我們將N個數每次不停的分兩堆，然後使兩堆有所對應的值，持續進行下去。以N = 6為例子:
1 2 3 4 5 6
      ^^^^^ (-3)
1 2 3 1 2 3
  ^^^   ^^^ (-2)
1 0 1 1 0 1 
^   ^ ^   ^ (-1)
0 0 0 0 0 0
透過分成一樣的兩堆，兩邊進行同樣的動作，即可算出最少的操作次數。至於為什麼分成兩堆是optimal，可以好好的思考一下～。
注　　意：無

代碼如下：

uva 11369 - Shopaholic

題目出處：Uva

題目連結：11369 - Shopaholic

題目大意：link(luckycat)

解題方法：很水的一題，思路是每三個就有一個能不用付錢，要省下最多的錢，那就盡量的讓越大的商品被省下越好。因此，先由大到小排序所有物品，再每三個一起付錢，每次能省下的肯定是當下能省的最多錢（greedy）。

注　　意：無

代碼如下：

uva 11310 - Delivery Debacle

題目出處：Uva

題目連結：11310 - Delivery Debacle

題目大意：link(luckycat)

解題方法：分析組合的情況。x代表空，o代表一單位的蛋糕，z代表為L形的蛋糕。

　　F[i]代表完整個寬度2長度i的組合數量，將他化簡成最左邊是填滿的情況。
　　F[i] = F[i-1] + 2*G[i-1] + 2*F[i-2]
　　x x x x　　　o x x x　　z z x x　　o z x x　
　　　　　　　 = 　　　　  + 　　　　　+
　　x x x x　　　o x x x　　z x x x　　z z x x
　　後兩個可以上下顛倒，因此要乘二。

　　G[i]代表缺一個，而總長度為i的組合數量。
　　G[i] = F[i-1] + F[i-2]
　　  x x　　　  x x　　  z x
　　　　　　=　　　　  +
　　x x x　　　o x x　　z z x

　　給定初始的F跟G即可解決此題。

注　　意：運算最大到10^18

代碼如下：