出處:https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=26&page=show_problem&problem=2395
解題策略:DP
提供每種燈泡的電壓V、電源費用K、每個燈泡費用C與數量L
dp[i]表示1到i種燈泡的最少花費
先將燈泡依照電壓由小到大排序,大電壓可以取代小電壓
使用第i種燈泡取代第j+1到i種的燈泡,公式如下
dp[i] = min(dp[i], dp[j] + (sum[i]-sum[j])*C[i] + K[i]) ,0<=j<=i