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

土下座しながら探索中

主に競技プログラミング

UVa 10520 : Determine it

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

問題概要:
短いので略

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

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

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


コード:

#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;
}