読者です 読者をやめる 読者になる 読者になる

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;
	}
}

参考文献

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

広告を非表示にする