Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-29SRM357 (Practice)

SRM 357 Hotel

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

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

  • 制約見てDPだと思った
  • 速度勝負だと思ったのでEgor風に提出してからデバッグを敢行した
import java.util.Arrays;

public class Hotel {

	public int marketCost(int minCustomers, int[] customers, int[] cost) {
		int[] dp = new int[5000];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		int len = customers.length;
		for (int i = 0 ; i < 5000 ; i++) {
			if (dp[i] != Integer.MAX_VALUE) {
				for (int j = 0 ; j < len ; j++) {
					int ti = i + customers[j];
					if (ti < 5000) {
						dp[ti] = Math.min(dp[ti], dp[i] + cost[j]);
					}
				}
			}
		}
		
		int res = Integer.MAX_VALUE;
		for (int i = minCustomers ; i < 5000 ; i++) {
			res = Math.min(res, dp[i]);
		}
		return res;
	}
}