UVa 10520 : Determine it

問題リンク：http://uva.onlinejudge.org/external/105/10520.html

問題概要：
短いので略

解法：
式に従って頑張ってノートでシュミレーションして見た結果左したのあたりから戻るように埋めていくとよさそう・・・

だがしかし今回nが20しかないので、
最大20*20で毎回埋めて行っても良い
一回20*20のループを回して更新できる場所を探す
すると少なくとも１つは必ず見つかる
なので最大でも20*20*20*20回で必ず終わる

あと、jが１の時どうなるのかが書いていない（自分が読み取れなかっただけかも）ので、
その場合は０を入れると良い

コード：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<climits>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf INT_MAX
#define MAX 30

using namespace std;

typedef long long ll;

ll a[MAX][MAX];
int n;

void compute(int j,int i)
{
  if(a[i][j] != inf)return;
  if(i < j)
    {
      ll cost = -inf;
      bool in = false;
      REP(k,i,j)
	{
	  in = true;
	  if(a[i][k] == inf || a[k+1][j] == inf)return;
	  cost = max(cost,a[i][k] + a[k+1][j]);
	}
      if(!in)cost = 0;
      if(cost == -inf)return;
      a[i][j] = cost;
      return;
    }
  else
    {
      ll cost_a,cost_b;
      cost_a = cost_b = -inf;
      if(i == n)cost_a = 0;
      else
	{
	  bool in = false;
	  REP(k,i+1,n+1)
	    {
	      in = true;
	      if(a[k][1] == inf || a[k][j] == inf)return;
	      cost_a = max(cost_a,a[k][1]+a[k][j]);
	    }
	  if(!in)cost_a = 0;
	  if(cost_a == -inf)return;
	}

      if(j == 0)cost_b = 0;
      else
	{
	  bool in = false;
	  REP(k,1,j)
	    {
	      in = true;
	      if(a[i][k] == inf || a[n][k] == inf)return;
	      cost_b = max(cost_b,a[i][k]+a[n][k]);
	    }
	  if(!in)cost_b = 0;
	  if(cost_b == -inf)return;
	}
      a[i][j] = cost_a + cost_b;
      return;
    }
}

int main()
{
  while(cin >> n)
    {
      rep(i,n+1)rep(j,n+1)a[i][j] = inf;
      cin >> a[n][1];


      bool update = true;
      while(update)
	{
	  update = false;
	  for(int y=n;y>=0;y--)
	    {
	      for(int x=0;x<=n;x++)
		{
		  if(a[y][x] == inf)
		    {
		      compute(x,y);
		    }
		  if(a[y][x] == inf)update = true;
		}
	    }  
	}

      cout << a[1][n] << endl;
    }
  return 0;
}