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