土下座しながら探索中

主に競技プログラミング

 AOJ 0145 : Cards

問題リンク : Cards | Aizu Online Judge

解法:
ほとんど連鎖行列積
コスト計算は連鎖行列積と異なるのでそこを変更するだけ
入力を保存した配列を pair p[] とすると、
コストは p[どこから].first*p[中間地点-1].second*p[中間地点].first*p[どこまで].second となる

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<28)
using namespace std;
typedef pair<int,int> ii;
ii p[200];
int n;

void solve()
{
  int M[n+1][n+1];
  rep(i,n+1)rep(j,n+1)M[i][j] = inf;
  rep(i,n+1)M[i][i] = 0;

  rep(j,n)//どこから
    {
      rep(i,n-j)//どこまで
	{
	  REP(k,i+1,i+j+1)//中間地点
	    {
	      int cost = M[i][k-1] + M[k][i+j] + p[i].first*p[k-1].second*p[k].first*p[i+j].second;
	      if(cost < M[i][i+j])
		  M[i][i+j] = cost;
	    }
	}
    }
  cout << M[0][n-1] << endl;
}

int main()
{

  while(cin >> n)
    {
      rep(i,n)cin >> p[i].first >> p[i].second;
      solve();
    }
  return 0;
}