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

土下座しながら探索中

主に競技プログラミング

AOJ 1222 : Telescope

AOJ 動的計画法

問題リンク : Telescope | Aizu Online Judge

問題概要:
n個の点が円上に存在する
その内m個を選んだ時にできる多角形の面積の最大値を求めよ

解法:
動的計画法で解いた
dp[始点となる点][最後に使った点][点を選んだ回数]:=その時の最大面積 とした

for sp 0..n            //始点
  for cnt 2..m         //点を選んだ回数
    for lp sp+1..n     //最後に選んだ点
      for np lp+1..n   //次に選ぶ点
        dp[sp][np][cnt+1] = max(dp[sp][np][cnt+1],
                                dp[sp][lp][cnt]+area(sp,lp,np)
/*
ここでarea(i,j,k)は三角形ijkの面積を返す
*/


コード:

typedef long double ld;
int n,m;
ld p[MAX];
ld area[MAX][MAX][MAX];//area[start point][last point][new point] := the area
ld dp[MAX][MAX][MAX];//dp[start point][last point][the number] := maximum area

double getArea(int i,int j)
{
  assert(i < n && j < n);
  return sin((p[j]-p[i])*2*PI)/2.0;//S = (b*c*sinA)/2,in this case, b = c = 1
}

void init_area()
{
  rep(i,n)//start point
    {
      REP(j,i,n)//last point
	{
	  REP(k,j,n)//new point
	    {
	      area[i][j][k] = getArea(i,j)+getArea(j,k)+getArea(k,i);
	    }
	}
    }
}

int main()
{
  while(cin >> n >> m,n|m)
    {
      rep(i,n)cin >> p[i];

      init_area();

      rep(i,MAX)rep(j,MAX)rep(k,MAX)dp[i][j][k] = -inf;
      rep(i,MAX)rep(j,MAX)dp[i][j][2] = 0;
      ld ans = -inf;
      rep(sp,n)//start point
	{
	  REP(cnt,2,m)//the number of uses
	    {
	      REP(lp,sp+1,n)//last point
		{
		  REP(np,lp+1,n)//new point
		    {
		      if(dp[sp][lp][cnt] == -inf)continue;

		      dp[sp][np][cnt+1] = max(dp[sp][np][cnt+1],
					      dp[sp][lp][cnt]+area[sp][lp][np]);
	
		     
		      if(cnt+1 <= m)
			ans = max(ans,dp[sp][np][cnt+1]);  
		    }
		}
	    }
	}

      cout << setiosflags(ios::fixed) << setprecision(6) << ans << endl;

    }
  return 0;
}