カード

パソコン甲子園 2006 カード

問題はこちら

連鎖行列積問題の解法と同様に動的計画法で解きます。

例えば、下図のように５枚のカードの山があるとします。



まず最初に、隣り合う２組の山を重ねるときの最小のコストを計算します（j = 1）。
i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。

つぎに、隣り合う３組の山を重ねるときの最小のコストを計算します(j = 2)。
i = 1, 2, 3 について計算します。

つぎに、隣り合う４組の山を重ねるときの最小のコストを計算します(j = 3)。
i = 1, 2 について計算します。

同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。
i = 1 について計算します。


各 j の値での最小コストの計算方法を考えます。
例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります：

• カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト　＋　それら２つの山を重ねるコスト　(k = i+1)
• カードの山[1,2]とカードの山[3,4]をそれぞれ重ねるのに要した最小コスト　＋　それら２つの山を重ねるコスト　(k = i+2)
• カードの山[1,2,3]とカードの山[4]をそれぞれ重ねるのに要した最小コスト　＋　それら２つの山を重ねるコスト　(k = i+3 = i+j)

#include<iostream>
using namespace std;
#define MAX 100
#define INFTY (1<<24)

struct Card{ int top, bottom; };

Card C[MAX+1];
int N;

int getCost(){
    int cost[MAX+1][MAX+1];
    for ( int i = 1; i <= N; i++ ){
        for ( int j = 1; j <= N; j++ ) cost[i][j] = INFTY;
    }
    for ( int i = 1; i <= N; i++ ) cost[i][i] = 0;

    for ( int j = 1; j <= N-1; j++ ){
        for ( int i = 1; i <= N-j; i++ ){
            for ( int k = i+1; k <= i+j; k++ ){
                int mul = C[i].top * C[k-1].bottom * C[k].top * C[i+j].bottom;
                cost[i][i+j] = min( cost[i][i+j], cost[i][k-1] + cost[k][i+j] + mul );
            }
        }
    }

    return cost[1][N];
}

main(){
    cin >> N;
    for ( int i = 1; i <= N; i++ ) cin >> C[i].top >> C[i].bottom;
    cout << getCost() << endl;
}