AOJ 0145 : Cards
問題リンク : Cards | Aizu Online Judge
解法:
ほとんど連鎖行列積
コスト計算は連鎖行列積と異なるのでそこを変更するだけ
入力を保存した配列を pair
コストは 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; }