2028 - Gather on the Clock

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2028

問題

１人用ゲームをする。
カードを表す数列が与えられるので、カードを円状に並べることを考える。
1. あるカードを選んで、そのカードを時計回りで次のカードの上に被せる。
2. このとき、その２つのカードの数字の差だけ加点される。
3. 被せたものは１つのカードとして扱う。
この操作をカードが１つになるまで繰り返す。
得られる最高得点を求めよ。

解法

※以下、本当ならば円状になっているので %n が必要な所があるが省略した。
ポイントは、ある区間のカードを１つにしたとき、１番上のカードは左端（反時計周りの端）のものになるということである。
よって、
DP[i][w] = [i,i+w]のカードを１つにするときの最大得点
としてDPができる。
DP[i][w]は、 j = 0...w-1 に関して [i,i+j]と[i+j+1,i+w-j-1]を組み合わせることを考えて求めることが出来る。
このとき、[i,i+j]の山の一番上はカードi、[i+j+1,i+w-j-1]の山の一番上はカードi+j+1である。

ソース

int a[100];
int dp[100][101];
int main() {
  int N;
  cin >> N;
  while(N--) {
    int n;
    cin >> n;
    REP(i, n) cin >> a[i];
    memset(dp,0,sizeof(dp));
    for (int w=1; w<n; ++w)
      REP(i, n)
        REP(j, w)
          dp[i][w] = max(dp[i][w], dp[i][j]+dp[(i+j+1)%n][w-j-1]+abs(a[i]-a[(i+j+1)%n]));
    int ans = 0;
    REP(i,n)
      ans = max(ans, dp[i][n-1]);
    cout << ans << endl;
  }
}