Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-02SRM353, SRM354 (Practice)

SRM 354 RemissiveSwaps

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

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

  • 素直にDPするだけ。
    • 3問の中で一番簡単かも
    • Math.pow(10, n)とかしてると定数倍に重く効いてくるので配列に持たせておくとよい
public class RemissiveSwaps {
	int[] memo = new int[1000001];
	int[] pidx = new int[]{1, 10, 100, 1000, 10000, 100000, 1000000};
	
	public int dfs(int now) {
		if (now == 0) {
			return 0;
		}
		if (memo[now] >= 1) {
			return memo[now];
		}
		
		int nn = now;
		int[] d = new int[7];
		int cnt = 0;
		for (int i = 0 ; i < 7 ; i++) {
			d[i] = nn % 10;
			nn /= 10;
			cnt++;
		}
		
		int max = now;
		for (int i = 0 ; i < cnt ; i++) {
			for (int j = i+1 ; j < cnt ; j++) {
				if (d[i] >= 1 && d[j] >= 1) {
					int tn = now;
					tn -= pidx[i] * d[i];
					tn -= pidx[j] * d[j];
					tn += pidx[i] * (d[j]-1);
					tn += pidx[j] * (d[i]-1);
					
					max = Math.max(max, dfs(tn));
				}
			}
		}
		
		memo[now] = max;
		return max;
	}
	
	
	public int findMaximum(int N) {
		if (N >= 1000000) {
			return 1000000;
		}
		return dfs(N);
	}
}