AOJ2028 Gather on the Clock

AOJ Volume20

問題リンク Gather on the Clock

  • 概要

N個の数字が円形にならんでいる。好きな数字Aを1つ選び、時計回りに1つ回った次の数字Bとの差の絶対値|A-B|が得点に加算される。この後、Bは円から無くなる。この操作を円に残った数字がただ1つになるまで続けたとき、得られる得点の最大値を答えよ。
2 <= N <= 100
0 <= 数字 <= 100

  • 解法

メモ化再帰で解きました。
dp[i][j]: 円のi番目の数字をj番目の数字まで動かしたときに得られる最大値
という表を用意します。dp[i][(i-1+N)%N]は、i番目の数字をすぐ後ろの場所まで動かしているので、円に残る最後の数字をiとしたときのスコアの最大値が求まっていることになります。答えとしては、これを全通り試してそのうちの最大値を取ったものになります。
dp[i][j]の埋め方の説明です。
i == jなら0です
(i+1)%N == jなら、iを1回動かすだけなのでabs(a[i]-a[j])がそのまま答えです
それ以外の場合、i < k < jのうちどれかをj番目まで動かした後、iをk番目まで動かせばいい(このkは既にj番目まで移動済みなのでj番目まで動かしていることになります）ので、
dp[i][k] + dp[k][j] (i < k < j)
が答えの候補です。更に、iをj-1番目まで動かす最善の手を打った後、iとjの差を計算する
dp[i][(j-1+N)%N] + abs(a[i]-a[j])
の動かし方も答えの候補です。これらの最大値を取ります。

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//Gather on the Clock
public class AOJ2028 {

	int n;
	int[] a;
	int[][] dp;
	
	int get(int i, int j){
		if(i==j)return 0;
		if(dp[i][j]!=-1)return dp[i][j];
		if((i+1)%n==j)return dp[i][j]=Math.abs(a[i]-a[j]);
		int res = get(i, (j-1+n)%n) + Math.abs(a[i]-a[j]);
		int k = (i+1)%n;
		while(k!=j){
			res = Math.max(res, get(i, k)+get(k, j));
			k = (k+1)%n;
		}
		return dp[i][j] = res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			n = sc.nextInt();
			a = new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			dp = new int[n][n];
			for(int[]d:dp)Arrays.fill(d, -1);
			int res = 0;
			for(int i=0;i<n;i++)res=Math.max(res, get(i, (i-1+n)%n));
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2028().run();
	}
}