読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 2028 : Gather on the Clock

AOJ

問題リンク:Gather on the Clock | Aizu Online Judge

問題概要:
n個(2 <= n <= 100)のノードが時計回りで円をつくるように並べられる
i番目のノードを時計回りでみて次のノードの上にかぶせるとき、i番目のノードと次のノードにかかれている値の差だけポイントがはいる
ノードが1つになるまでその操作を繰り返した時に手に入れることができるポイントの最大値をもとめよ

使用した言語:C++

解法:
DPでといた
int dp[n][n]という2次配列をつくっておき、
dp[i][j] := ノードiからノードjまでの最大値 と定義しておく
i番目のノードから(i+1)%n番目のノードまでの最大値はi番目のノードの値から(i+1)%n番目のノードの値を引いたものの絶対値なのであらかじめ入れておく
その後
for i 2からn-1まで //幅
for j 0からnまで //ノードの番号
for k jからj+i-1まで //中間地点
というループでdp配列をうめてゆく
k == j の時は
dp[j][(j+i)%n] = max(dp[j][(j+i)%n],dp[j][(j+i-1)%n]+abs(vec[j]-vec[(j+i)%n])) となり、
それ以外は
dp[j][(j+i)%n] = max(dp[j][(j+i)%n],dp[k%n][(j+i)%n]+dp[j][k%n]) となる

k == jの時はj番目のノードを(j+i)%n番目のノードにのせたときの最大値を求めている

コード:

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;

int main()
{
  int N;
  scanf("%d",&N);
  while(N-- > 0)
    {
      int n;
      cin >> n;
      int dp[n][n];
      int vec[n];
      for(int i=0;i<n;i++)
	{
	  cin >> vec[i];
	  for(int j=0;j<n;j++)
	    dp[i][j] = 0;
	}
      
      int mex = 0;
      for(int i=0;i<n;i++)
	dp[i][(i+1)%n] = abs(vec[i]-vec[(i+1)%n]),mex = max(mex,dp[i][(i+1)%n]);
      
      for(int i=2;i<n;i++)//幅
	{
	  for(int j=0;j<n;j++)//index
	    {
	      for(int k=j;k<=j+i-1;k++)//中間地点
		{
		  if(k == j)
		    {
		      dp[j][(j+i)%n] = max(dp[j][(j+i)%n],dp[j][(j+i-1)%n]+abs(vec[j]-vec[(j+i)%n]));
		      mex = max(mex,dp[j][(j+i)%n]);
		      continue;
		    }
		  dp[j][(j+i)%n] = max(dp[j][(j+i)%n],
				       dp[k%n][(j+i)%n]+dp[j][k%n]);
		}
	      mex = max(mex,dp[j][(j+i)%n]);
	    }
	}

      cout << mex << endl;


    }
  return 0;
}