AOJ 0145 Cards

問題

問題リンク

解法

ある区間内の山をすべて重ねたとする。このとき山の順序は変わらないので最終的にできる山の状態は、その重ねる順序によらない。

よって、区間を決めれば操作順を無視できるので、その最小コストのみが分かっていればよい。また、ある区間同士をマージするときのコストは、その区間の両端の値のみで求められる。

以上の考察から区間DPでこの問題が解けることがわかる。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int IINF = INT_MAX;
 
int n, a[105], b[105], dp[105][105];  // dp[i][j]=区間[i,j]の山をつくる最小コスト
 
int rec(int l, int r){
    if(dp[l][r] != -1) return dp[l][r];
    if(r==l) return 0;
 
    int res = IINF;
    for(int i=l;i<r;i++){
        res = min(res, rec(l,i) + rec(i+1,r) +a[l]*b[i]*a[i+1]*b[r]);
    }
    return dp[l][r] = res;
}
 
int main() {
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
    }
    for(int i=0;i<n;i++) fill(dp[i], dp[i]+n, -1);
    cout << rec(0,n-1) << endl;
    return 0;
}