FenceRepair
問題概要
とても長い板からN個の板を切り出す。
切り出す板はL1,L2,...Lnであり、元の板の合計となっている。
板を切断する際に、その板の長さだけコストがかかる。
例えば21の板を13と8に分けた場合、コストは13+8である。
最小コストで板を切り出した場合のコストを出力せよ。
入力 N:切り出す板の数 L:切り出す板の長さの配列
出力 cost:コスト
問題解法
常に切り出す場合、二つの板が出現し、コストはその合計となる。
切り出す板を短い順に並べて(一番切り出すのに回数が必要)、先頭二つをまず切り出す。
次に、切り出した二つを合計したものを、2つの板の代わりに配列へ入れて、再度ソート。
これを再帰的に行うことで、解を得る。
回答コード(C#)
class John { public int Repair (int N, int[] L) { int cost = 0; while (N > 1) { Array.Sort (L); cost += L [0] + L [1]; L [0] = cost; L [1] = 0xFFFF; N--; } return cost; } }