【DPメニュー】最安値を達成するには 3 (paizaランク B)-解答例-PHP編

2022年8月15日

【DPメニュー】> 【最安値】STEP: 3 最安値を達成するには 3 (paizaランク B 相当) [難易度: 1717 ±20]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

八百屋にて、りんご x 個が a 円で、りんご y 個が b 円で売られています。

りんごの買い方を工夫したとき、最終的に n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

入力値（例）
4 2 110 5 200

出力値（例）
200

解答例

<?php
    list($n, $x, $a, $y, $b) = explode(" ", trim(fgets(STDIN)));
    
    $dp[0] = 0;
    
    for ($i = 1; $i <= ($n + $y); $i++) {
        $dp_a = $i > $x ? $dp[$i - $x] + $a : $a;
        $dp_b = $i > $y ? $dp[$i - $y] + $b : $b;
        
        $dp[$i] = min($dp_a, $dp_b);
    }
    
    echo $dp[$n];
?>

<?php

list($n, $x, $a, $y, $b) = explode(" ", trim(fgets(STDIN)));

$dp[0] = 0;

for ($i = 1; $i <= ($n + $y); $i++) {

$dp_a = $i > $x ? $dp[$i - $x] + $a : $a;

$dp_b = $i > $y ? $dp[$i - $y] + $b : $b;

$dp[$i] = min($dp_a, $dp_b);

}

echo $dp[$n];

解答例

カテゴリー