AOJ : 0145 - Cards

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0145&lang=jp
日本語の問題文があるので説明は省略です.

アルゴリズム

↓この方のプログラムを参考にときました. 結果的にほとんどマネてます.
http://d.hatena.ne.jp/tnn-jp/20091107/1257579814

動的計画法
dp[範囲の左端インデックス][範囲の右端インデックス] で管理.

3重ループをまわしているのは,
範囲の幅の決定(i) -> 範囲の左端インデックス決定(j) -> 山の重ね合わせ位置(k)

漸化式は,
dp[j][j+i] = min(dp[j][j+i], a[j]*b[k]*a[k+1]*b[j+i] + dp[j][k] + dp[k+1][j+i]);

すみません.
さっさと寝たいがために解説が適当です.(4:00)

プログラム

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)
#define EREP(i,n,m) for(int i=n;i<=m;i++)
#define erep(i,n) EREP(i,0,n)

typedef pair<int,int> P;

unsigned int dp[101][101];

int main(void){
  int n; cin>>n;
  vector<P> v(n);
  rep(i,n) cin>>v[i].first>>v[i].second;

  erep(i,n){
    erep(j,n) dp[i][j] = INT_MAX;
    dp[i][i] = 0;
  }

  REP(i,1,n){ //幅の決定
    EREP(j,0,n-i){ //開始位置の決定
      REP(k,j,j+i){ //切断位置の決定
        int cost = v[j].first * v[k].second * v[k+1].first * v[j+i].second;
        dp[j][j+i] = min(dp[j][j+i],cost+dp[j][k]+dp[k+1][j+i]);
      }
    }
  }

  cout<<dp[0][n-1]<<endl;

  return 0;
}