網頁

2014年5月26日 星期一

UVa 11218 KTV

題意:
    總共有9個人(編號1~9)要分成3組唱歌,每組3個人,每個人只能唱一次。第一行N表示底下有N種組合,每種組合a,b,c,s,前三個是人員編號,s是該組合的分數。從N種中任選三種組合使得1~9號都能唱到歌,並且使得分數的和最高,輸出該分數,如果找不到組合滿足大家都能唱到歌則輸出-1。

想法:
    bitmask,(1<<9)-1表示所有人都唱的到歌的狀態,二進位來看就是(111111111)2,dp[i]=j表示在狀態i的情況下最高分數為j,因此dp[(1<<9)-1]就是所有人唱的到歌的最高分數。
    用dfs來枚舉不同組合,當人員沒有重複的時候才能將兩個狀態合併在一起,例如(000000111)2和(000111000)2這兩個狀態可以合併變成(000111111)2,並去更新dp[(000111111)2]的分數,不斷更新所有可能的合併來枚舉所有情況。