読者です 読者をやめる 読者になる 読者になる

AOJ 0145 Cards

問題概要

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;
}