Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-05SRM300台を練習していく part7

SRM 316 PlacingPieces

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

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

難しい。解いたのはだいぶ前だけど今やれって言われたら多分出来ない


public class PlacingPieces {

	public int optimalPlacement(int L, int[] pieces) {
		java.util.Arrays.sort(pieces);
		int len = pieces.length;
		int ans = len;
		if (pieces[0] > L) {
			return 0;
		}

		for (int p = 0 ; p < len ; p++) {
			boolean[][][] dp = new boolean[31][31][1001];
			int inilen = 0;
			for (int i = 0 ; i < p ; i++) {
				inilen += pieces[i];
			}
			if (inilen >= L) {
				break;
			}
			dp[p][p][inilen] = true;
			for (int i = 0 ; i < len ; i++) {
				for (int n = 0 ; n <= len ; n++) {
					for (int l = 0 ; l <= L ; l++) {
						if (dp[i][n][l]) {
							dp[i+1][n][l] = true;
							if (p != i && l + pieces[i] <= L) {
								dp[i+1][n+1][l+pieces[i]] = true;
							}
						}
					}
				}
			}

			for (int n = 0 ; n <= len ; n++) {
				for (int l = L ; l >= 0 ; l--) {
					if (dp[len][n][l] && L-l < (n+1)*pieces[p]) {
						ans = Math.min(ans, n);
					}
				}
			}
		}
		return ans;
	}
}