AOJ 0145 Cards

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145

問題概要

n 個のカードの山がある．カードには数字がかかれている．
それぞれの山の一番上と下のカードの数字は a(i) と b(i) である．
2つの山を重ねる操作を繰り返して，一つの山にすることを考える．
2つの山を重ねる時，それらの山の一番上と下にある4つのカードの数字を全てかけ合わせた値だけコストがかかる．
また，重ねる場合は，必ず左の山を上に，右の山を下にする．
この時，1つの山にするために必要なコストを最小化せよ．

制約

1 <= n <= 100
1 <= a(i), b(i) <= 200

解法

dp[i][j] := i 番目の山から j 番目の山までを1つの山にするために必要な最小のコスト
とする動的計画法で解ける．
ただし，dp[i][i] = 0 である．
dp[i][j] を求めるとき，i <= k < j なる各 k について考える．
すると，dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + a(i) * b(k) * a(k+1) * b(j)) という式が成り立つ．
（なぜなら，左の山は必ず上に重ねるから．）
これを i, j の幅を少しずつ増やしていけば，dp[0][n-1] が求める答えとなる．
計算量は O(n^3)．

ソースコード

#include <iostream>
#include <vector>
using namespace std;
 
using ll = long long;
 
constexpr ll INF = 1e18;
 
int main() {
    int n;
    cin >> n;
    vector<vector<ll>> dp(n, vector<ll>(n, INF));
    vector<ll> a(n), b(n);
    for(int i=0; i<n; ++i) {
        cin >> a[i] >> b[i];
    }
    for(int i=0; i<n; ++i) {
        dp[i][i] = 0;
    }
    for(int w=1; w<n; ++w) {
        for(int i=0; i+w<n; ++i) {
            for(int j=i; j<i+w; ++j) {
                dp[i][i+w] = min(dp[i][i+w], dp[i][j] + dp[j+1][i+w] + a[i]*b[j]*a[j+1]*b[i+w]);
            }
        }
    }
    cout << dp[0][n-1] << endl;
}