# ほぼ他の方のサンプルを見て理解しようとしながら写しただけみたいな・・・ # use List::Util 'min'; # N V # C1 .. Cn $INF = 10e16; $input=; chomp($input); @input=split(/ /, $input); $fruits_type_count=@input[0]; $goal_liter=@input[1]; $input=; chomp($input); @fruit_costs=split(/ /, $input); $cost_summary = 0; for($i=0;$i<@fruit_costs;$i++) { $cost_summary += $fruit_costs[$i]; } if( $goal_liter <= $fruits_type_count ) { # 目標値がフルーツの種類の数以下ならば # すべてのフルーツを1リットル買って終了 print "$cost_summary\n"; exit(0); } # 果物のコストを、下記のように集計する # sum[k] = cost[0] + cost[1] + ... + cost[k] # その意味は、 # kを1個買うとき、それより小さいindexの果物もすべて最低で1つは買わなければならない # (indexが小さいものほど、量が多いというルールだから) # そのため、kを1個買うということは、それ以下indexのすべてのジュースを1個ずつ買うということになり、 # この集計結果は、それを考慮した(k以下のすべてのジュースも1個ずつ買った金額の集計になった)金額になっているということ? # それを使えば、kのジュースを買う場合の最小の額でルールが満たされる事にもなる # 集計の配列 @sum_fruit_costs=(@fruit_costs[0]); for($i=1;$i < @fruit_costs; $i++) { push( @sum_fruit_costs, $sum_fruit_costs[$i-1] + $fruit_costs[$i] ); } # とりあえずまあ、全部一個ずつ買った状態にする # それも最低条件の1つ # print(acc_fruit_costs[fruits_type_count-1]) $alreadyCaluculatedCost = $cost_summary; $goal_liter-=$fruits_type_count*1; # さらに、目標値が大きい場合、通常のdpでは時間がかかりすぎるので、目標値を削る # 基本的に、同じリットルを買った際に一番コストの小さいフルーツをできるだけたくさん買う。 # リットル単価の安い物? # 全部のフルーツを舐められるギリギリくらいまでリットルを残せばその方法で減らせるはず? $minCostIndex=0; for($i=0; $i < @sum_fruit_costs;$i++) { if( $sum_fruit_costs[$i] * ($minCostIndex+1) < $sum_fruit_costs[$minCostIndex] * ($i+1) ) { $minCostIndex = $i; } } # print( $minCostIndex."\n"); # 上記で、最もコストが小さいものを求めた # ラスト100個(フルーツ数個)のフルーツを選べれば良いレベルまで減らして良い? # 多分、ラスト100個はフルーツのリットル単価のみでは計算できない # つまり、すべてのフルーツ(100個)を舐められるだけのリットル(フルーツ数2乗+フルーツ数くらいあれば良い?)を残してそのフルーツを買う # 多分・・・多分・・・ $literCalcByDp = $fruits_type_count**2 + $fruits_type_count; $minCostFruitBoughtCount = 0; if( 0 < $goal_liter - $literCalcByDp ) { # ある程度($literCalcByDp)よりも目標リットルが大きい # 上記方法でそこまで削減する $minCostFruitBoughtCount = int(($goal_liter - $literCalcByDp) / ($minCostIndex+1)); } $goal_liter -= $minCostFruitBoughtCount * ($minCostIndex+1); $alreadyCaluculatedCost += $minCostFruitBoughtCount * $sum_fruit_costs[$minCostIndex]; # print( "\n".$goal_liter."\n"); # print( $alreadyCaluculatedCost."\n"); print($minCostFruitBoughtCount*($minCostIndex+1)."\n"); # dp用配列定義 $arr_count = $goal_liter * $fruits_type_count; @dp = ($INF)x$arr_count; $dp[0]=0; # dp for( $i=0; $i<$goal_liter; $i++ ) { # iリットル時の最小コスト for( $j=0; $j<$fruits_type_count; $j++ ) { # 全種類のフルーツをループ # フルーツ(index=$j)を加えた時の最小コスト if( $dp[$i] + $sum_fruit_costs[$j] < $dp[$i+$j+1]) { $dp[$i+($j+1)] = $dp[$i] + $sum_fruit_costs[$j]; } } } print $alreadyCaluculatedCost + $dp[$goal_liter]."\n";