Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 340 ProblemsToSolve

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

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

  • 動的計画法
    • 座標圧縮して [現在位置][最大][最小] でDPする
import java.util.Arrays;

public class ProblemsToSolve {
	public int minNumber(int[] pn, int variety) {
		int len = pn.length;
		int[] pmap = new int[1001];
		int[] idxscore = new int[1001];
		Arrays.fill(pmap, -1);
		int pidx = 0;
		for (int x : pn) {
			if (pmap[x] == -1) {
				pmap[x] = pidx;
				idxscore[pidx] = x;
				pidx++;
			}
		}
		
		int[][][] dp = new int[len][pidx][pidx];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				Arrays.fill(dp[i][j], 10000);
			}
		}
		dp[0][pmap[pn[0]]][pmap[pn[0]]] = 1;
		
		int min = len;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				for (int k = 0 ; k < pidx ; k++) {
					if (dp[i][j][k] >= 10000) {
						continue;
					}
					for (int go = i + 1 ; go <= i + 2 ; go++) {
						if (go >= len) {
							continue;
						}
						
						int solve = dp[i][j][k] + 1;
						int wmin = Math.min(idxscore[j], pn[go]);
						int wmax = Math.max(idxscore[k], pn[go]);
						if (wmax - wmin >= variety) {
							min = Math.min(min, solve);
						}
						int tj = pmap[wmin];
						int tk = pmap[wmax];
						if (dp[go][tj][tk] > solve) {
							dp[go][tj][tk] = solve;
						}
					}
				}
			}
		}
		return min;
	}
}