#37909: 我的思路


s11104220@school.saihs.edu.tw (施同學)

School : 臺北市立松山高級工農職業學校
ID : 221254
IP address : [118.165.27.136]
Last Login :
2024-08-27 03:46:40
e465. 置物櫃分配 -- 2018年10月APCS | From: [118.165.1.197] | Post Date : 2023-10-17 20:48

dp(0,sum(array))=dp(1,sum(array)-a[0])+dp(1,sum(array))=....

dp1=2 4 8 16...類似二元樹

我使用stack解題

如果dp(idx,now) idx超出範圍 則判斷目前數值是否為大於最優解的最小值

如果找到大於最優解 減了目前索引的值會小於最優解 則判斷目前數值是否為大於最優解的最小值 並且不把dp(idx+1,now-a[i])加入stack

如果找到等於最優解 直接印出最低需求並break

 

提醒:

m為你有的櫃子 不是借出的所有櫃子總和

不會像範例測資一樣借出總和跟m一樣

 
ZeroJudge Forum