天才火消しエンジニア霧島 動的計画法での試み

ナップサック問題の解法で有名な動的計画法を使ってやってみました。

<?php
//メイン処理
$arrSitauke = array();              //下請け会社の組み合わせ配列
$need_se_num = trim(fgets(STDIN));  //必要なプログラマ(SE)の人数
$sitauke_total = trim(fgets(STDIN)); //下請け会社の総数
if ($need_se_num > 200000 || $sitauke_total > 50) {
    exit("\n");
}
for ($si = 0; $si < $sitauke_total; $si++) {
    $arrSitauke[] = explode(" ", trim(fgets(STDIN)));
}
//動的計画法
$arrNapsack = array(0 => 0);
for ($i = 0, $i_max = sizeof($arrSitauke); $i < $i_max; $i++) {
    $se_num = $arrSitauke[$i][0];
    $price = $arrSitauke[$i][1];
    foreach ($arrNapsack as $num => $nap_price) {
        if ($num >= $need_se_num)   //もう既に必要人数がいるのでこれ以上計算する必要がない
            continue;
        if (!isset($arrNapsack[$num + $se_num]) || $arrNapsack[$num + $se_num] >= $nap_price + $price) {
            $arrNapsack[$num + $se_num] = $nap_price + $price;
        }
    }
}
//コストが低い順に並べ替える
asort($arrNapsack);
//必要条件以上の人数が最初に出てきた価格が最安値
foreach ($arrNapsack as $num => $price) {
    if ($num >= $need_se_num) {
        exit("$price\n");
    }
}
exit("\n");

ケース7で3秒ぐらいかかります。
0.01秒の解法は深さ優先探索で枝刈りすればいけます。
http://paiza.jp/poh/kirishima/result/ce274bd444dbf960569ea2fdab310ea0