UVa 348 : Optimal Array Multiplication Sequence

問題リンク：Optimal Array Multiplication Sequence

問題概要：
N個の行列が与えられる
それらの行列を最適に計算するための括弧付けを行え

解法：
連鎖行列積
アルゴリズムイントロダクションを読んで勉強

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define all(n) (n).begin(),(n).end()
#define eps (1e-10)
#define equals(a,b) (fabs((a)-(b))<eps)
#define MAX 200
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;

int N,CNT = 1;
int s[MAX][MAX];


void print(int s[MAX][MAX],int i,int j)
{
  if(j != i)
    {
      printf("(");
      print(s,i,s[i][j]);
      printf(" x ");
      print(s,s[i][j]+1,j);
      printf(")");
    }
  else 
    printf("A%d",i);
}

void compute(int *p)
{
  int mincost[N+1][N+1];
  rep(i,N+1)mincost[i][i] = 0;
  
  for(int len=2;len<=N;len++)
    {
      for(int i=1;i<=N-len+1;i++)
	{
	  int j = i + len - 1;
	  mincost[i][j] = inf;
	  for(int k=i;k<j;k++)
	    {
	      int cost = mincost[i][k] + mincost[k+1][j] + p[i-1]*p[k]*p[j];
	      if(cost < mincost[i][j])
		{
		  mincost[i][j] = cost;
		  s[i][j] = k;
		}
	    }
	}
    }
  printf("Case %d: ",CNT++);
  if(N == 1)printf("(");
  print(s,1,N);
  if(N == 1)printf(")");
  puts("");
}

int main()
{
  while(scanf("%d",&N),N)
    {
      int p[N+1],h,w;
      rep(i,N)
	{
	  scanf("%d %d",&h,&w);
	  if(i == 0)p[i] = h,p[i+1] = w;
	  else p[i+1] = w;
	}

      compute(p);
      
    }
  return 0;
}