UVA - 11218 KTV

....太久沒寫扣 卡超久XDDDD

很不漂亮的寫法

題意就是9個人要分3堆 給你很多種組合的分數 問你分3堆(9個人都要分)的最高總分

我用dynamic programming, 紀錄某幾個人被選擇時的最高分

題目的input存成dp3[x] 表示選這3個人的最高分
x用bit壓縮紀錄是哪3個人 例如(1, 3, 6)的分數是10 則 dp3[0001001010(二進位)] = 10 (1<<1 + 1<< 3 + 1<< 6)

然後去算dp6(所有6個人分法的最高分)的所有情況 再算 dp6+dp3的組合 即可知道9個人都有分的最高總分

好啦我再說什麼我也不太清楚(哭) 直接用一個dp陣列維護就好 懶得改惹(還要判斷人數)

代碼+-看：

LeetCode - 307. Range Sum Query - Mutable

出處：LeetCode

延伸閱讀：統計的力量

看上面網址學的 摳起來超短... 不過邊界我沒處理就過了 a___a

bit世界的廣闊...

代碼：

uva 10000 - Longest Paths

題目出處：Uva

題目連結：10000 - Longest Paths

題目大意：link(luckycat)，有向無環圖，給起點找最遠路徑長度並且是哪個點。

解題方法：BFS，若點的最遠距離更新，則需再跑一次。
網路上有說可以用Floyd-Warshall即可解。

注　　意：一開始粗心用DFS吃TLE，因為邊數可以很多。

代碼如下：