AOJ 0145 - Cards

問題文 : カード

解法 :

dp(l, r) -> 区間(l, r)のカードを併合するために必要な最小コスト

とすると, l番目のカードが最も上に, r番目のカードが最も下になるのは明らかなので

dp(l, r) = min(dp(l, r), dp(l, i) + dp(i+1, r) + a[l] * b[i] * a[i+1] * b[r]) (l≦i＜r)

と計算できる.

コード :

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

int a[100], b[100];
int memo[100][100]; 

int getMin(int l, int r)
{
	int ans = INT_MAX;
	
	if (l == r) return (0);
	if (memo[l][r] >= 0) return (memo[l][r]);
	
	for (int i = l; i < r; i++){
		ans = min(ans, getMin(l, i) + getMin(i + 1, r) + a[l] * b[i] * a[i + 1] * b[r]);
	}
	
	return (memo[l][r] = ans);
}

int main()
{
	int n;
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		scanf("%d %d", &a[i], &b[i]);
	}
	memset(memo, -1, sizeof(memo));
	
	printf("%d\n", getMin(0, n - 1));
	
	return (0);
}