Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-09SRM383,384,385 (Practice)

SRM 383 Planks

|  SRM 383 Planks - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 383 Planks - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8396

  • 方針を検討
    • 切る長さを決め打ちして全探索でいこう
  • 実装
    • 切る長さでちょうど割り切れる場合に注意する。うなうな
  • 最後のサンプルだけ通らない。
    • 切らないほうが得する場合もあるのか
    • サンプル親切だなぁ
    • ある板について、切断コストが得られる利益を上回ってればパスするよう変更
  • 提出
public class Planks {

	public int makeSimilar(int[] lengths, int costPerCut, int woodValue) {
		int max = 0;
		int len = lengths.length;
		for (int l = 1 ; l <= 10000 ; l++) {
			int pieces = 0;
			int costs = 0;
			for (int i = 0 ; i < len ; i++) {
				if (lengths[i] < l) {
					continue;
				} else {
					int p = lengths[i] / l;
					int c = p;
					if (lengths[i] % l == 0) {
						c--;
					}
					if (p * woodValue * l <= costPerCut * c) {
						continue;
					}
					pieces += p;
					costs += c;
				}
			}
			max = Math.max(max, woodValue * pieces * l - costPerCut * costs);
		}
		return max;
	}
}