#29255: 解法三


SUNGOD (黑龍炎使.煞氣ㄟSUNGOD)

School : 國立臺灣海洋大學
ID : 95834
IP address : [123.240.145.218]
Last Login :
2023-01-27 20:42:44
d682. TOI2010 第三題:職棒簽約問題 -- 2010TOI研習營初選 | From: [123.240.145.218] | Post Date : 2022-02-09 14:50

DFS+剪枝

令dfs(int it,int v,int pw)

其中it/v/pw分別代表 目前看到第it個位子/用了v塊錢/總戰力為pw

初始態dfs(0,0,0),(選手的金額為v,戰力為w)

每一層it對每個選手都做一次dfs   //dfs(it+1,v+player[it][i].v,pw+player[it][i].w);

這裡有個細節,因為可以不選,所以還要再dfs一次  //dfs(it+1,v,pw);

基本上紀錄最大的合法pw就可以不WA了

複雜度:時間O(N^M)//呵呵你沒看錯,所以要剪枝

空間O(N*M)

 

剪枝一:當v花的比M還多時,不管怎麼跑都不可能是答案,直接return

剪枝二:紀錄最佳解,這需要用到解法二的概念,令DP[5005][N]表示看完N個人的情況下到達戰力pw所花的最少錢,當你目前花的錢超過時就可以return了 //不過空間又變成了O(S*N)

基本上只用上面兩個就能AC了(17ms)

剪枝三:排序選手,對每層的選手按照CP值(戰力/金額)從大到小排序,DFS的樹會小一點,因為後面比較差的選手會被剪枝二給減掉

 

 
ZeroJudge Forum