Problem:


カード

正の整数が書かれた一組のカードがあります。カードを積んで山をいくつか作り、それらを横一列に並べます。その中から隣り合った 2 つのカードの山を選び、右側の山の上に左側の山をそのまま重ねます。この操作をカードの山が一つになるまで繰り返していきます。

2 つのカードの山を重ねる時にそれらの一番上と下のカードに書かれた数をすべて掛け合わせます。こうして得られた数をカードの重ね合わせのコストと呼ぶことにします。カードの山を一つにするためのコストはすべての重ね合わせのコストを足し合わせたものとします。

どのような順番でカードの山を重ねるかでコストは変わります。たとえば、3 つのカードの山がある場合を考えます。それらの一番上と下のカードに書かれた数が，左側の山から順にそれぞれ 3 と 5, 2 と 8, 5 と4 だったとします。このとき，はじめに左と真ん中の山を重ねたときのコストは、3 × 5 × 2 × 8 = 240 です。この重ね合わせによって、一番上のカードが 3 で一番下のカードが 8 である山ができます。

この山を右の山の上に重ねると、そのコストは 3 × 8 × 5 × 4 = 480 になります。したがって、この順番でカードの山を一つにまとめたときのコストは 240 + 480 = 720 です。（図1）

一方、はじめに真ん中と右の山を重ねてから最後に左の山を重ねることにすると、そのときのコストは 2 × 8 × 5 × 4 + 3 × 5 × 2 × 4 = 440 になります。したがって，後の場合のように重ねた方がコストが小さくなります。（図2）

カードの山の個数とそれぞれの山の一番上と下のカードに書かれた数を入力とし、カードの山を一つにまとめるのに必要な最小のコストを出力するプログラムを作成してください。ただし、山の個数は 100 個以下とし、入力されるデータはどのような順番でコストを計算しても 231-1 を超えることはありません。

Input

入力は以下の形式で与えられます。

n
a1 b1
a2 b2
:
an bn

1 行目にカードの山の個数 n(n ≤ 100)、続く n 行に左から i 番目の山の 1 番上のカードに書かれた数 ai (1 ≤ ai ≤ 200) と 1 番下のカードに書かれた数 bi (1 ≤ bi ≤ 200) が与えられます。

Output

カードの山を一つにまとめるのに必要な最小のコストを１行に出力してください。

Sample Input

3
3 5
2 8
5 4

Output for the Sample Input

440



Sample input:
3
3 5
2 8
5 4


Sample output:
440

Submission status: Wrong Answer

Solution code:
def solve(Card):
  n = len(Card)
  if n==2: return 0
  A = Card[1:n][:]
  m = max(A)
  I = A.index(m)+1
  I2 = I/2*2
  cost = reduce(lambda a,b: a*b, Card[I2:I2+4])
  return cost+solve(Card[:I]+Card[I+2:])
    
d={}
n = int(raw_input())
Card=[]
for _ in [0]*n: Card += map(int,raw_input().split())
print solve(Card)

Submission status: Wrong Answer

Solution code:
def solve(Card):
  n = len(Card)
  if n==2: return 0
  x=[]
  for i in range(0,n-2,2):
    tmp = Card[:]
    T = tuple(Card[i:i+4])
    if T in d: cost = d[T]
    else:
      cost = reduce(lambda a,b: a*b, T)
      d[T] = cost
    tmp[i+1:i+3]=[]
    x.append(cost+solve(tmp))
  return min(x)

Submission status: Wrong Answer

Solution code:
def dfs(l, r):
    if (l, r) in cache:
        return cache[(l, r)]
    if l == r:
        return 0
    cache[(l, r)] = min(dfs(l, m) + dfs(m + 1, r) + L[l][1] * L[m][0] * L[m + 1][1] * L[m + 1][0] for m in xrange(l, r))
    return cache[(l, r)]

cache = {}
L = [map(int, raw_input().split()) for _ in xrange(input())]
print dfs(0, len(L) - 1)

Submission status: Wrong Answer

Solution code:
def dfs(l, r):
    if (l, r) in cache:
        return cache[(l, r)]
    if l == r:
        return 0
    cache[(l, r)] = min(dfs(l, m) + dfs(m + 1, r) + L[l][1] * L[m][0] * L[m + 1][1] * L[r][0] for m in xrange(l, r))
    return cache[(l, r)]

cache = {}
L = [map(int, raw_input().split()) for _ in xrange(input())]
print dfs(0, len(L) - 1)

Submission status: Wrong Answer

Solution code:
def dfs(l, r):
    if l == r:
        return 0
    if (l, r) in cache:
        return cache[(l, r)]
    cache[(l, r)] = min(dfs(l, m) + dfs(m + 1, r) + L[l][1] * L[m][0] * L[m + 1][1] * L[r][0] for m in xrange(l, r))
    return cache[(l, r)]

cache = {}
L = [map(int, raw_input().split()) for _ in xrange(input())]
print dfs(0, len(L) - 1)

Submission status: Time Limit Exceeded

Solution code:
def solve(Card):
  if len(Card)==1: return 0
  X = []
  for i in range(len(Card)-1):
    A = Card[:]
    tmp = A[i]+A[i+1]
    cost = reduce(lambda a,b: a*b, tmp)
    tmp[1:3] = []
    A[i:i+2] = [tmp]
    X.append(cost+solve(A))
  return min(X)
    
n = int(raw_input())
Card = [map(int,raw_input().split()) for _ in [0]*n]
print solve(Card)

Submission status: Time Limit Exceeded

Solution code:
def solve(Card):
  if len(Card)==1: return 0
  X = []
  for i in range(len(Card)-1):
    A = Card[:]
    tmp = tuple(A[i]+A[i+1])
    if tmp in d: cost = d[tmp]
    else:
      cost = reduce(lambda a,b: a*b, tmp)
      d[tmp] = cost
    tmp = list(tmp)
    tmp[1:3] = []
    A[i:i+2] = [tmp]
    X.append(cost+solve(A))
  return min(X)
    
d={}
n = int(raw_input())
Card = [map(int,raw_input().split()) for _ in [0]*n]
print solve(Card)

Submission status: Time Limit Exceeded

Solution code:
def solve(Card):
  n = len(Card)
  if n==2: return 0
  x=[]
  for i in range(0,n-2,2):
    tmp = Card[:]
    T = tuple(Card[i:i+4])
    if T not in d: d[T] = reduce(lambda a,b: a*b, T)
    tmp[i+1:i+3]=[]
    x.append(d[T]+solve(tmp))
  return min(x)
    
d={}
n = int(raw_input())
Card=[]
for _ in [0]*n: Card += map(int,raw_input().split())
print solve(Card)

Submission status: Time Limit Exceeded

Solution code:
n = input()
C = [map(int, raw_input().split()) for i in xrange(n)]
memo = {(i, i): 0 for i in xrange(n)}
def calc(i, j):
    if (i, j) in memo:
        return memo[i, j]
    return min(calc(i, k) + calc(k+1, j) + C[i][0]*C[k][1]*C[k+1][0]*C[j][1] for k in xrange(i, j))
print calc(0, n-1)

Submission status: Time Limit Exceeded

Solution code:
min_cost = 10000000


def compute_cost(card1, card2):
    return card1[0] * card1[1] * card2[0] * card2[1]


def rec(cards, cost):
    global min_cost
    if len(cards) == 1:
        min_cost = min(min_cost, cost)
        return
    for i in range(len(cards)-1):
        cpy = cards[:]
        cost1 = compute_cost(cards[i], cards[i+1])
        card = [cards[i][0], cards[i+1][1]]
        del cards[i]
        del cards[i]
        cards.insert(i, card)
        rec(cards, cost+cost1)
        cards = cpy[:]

n = input()
cards = [map(int, raw_input().split()) for i in range(n)]
rec(cards, 0)
print min_cost

Submission status: Time Limit Exceeded

Solution code:
def dfs(l, r):
    if (l, r) in cache:
        return cache[(l, r)]
    if l == r:
        return 0
    return min(dfs(l, m) + dfs(m + 1, r) + L[l][1] * L[m][0] * L[m + 1][1] * L[m + 1][0] for m in xrange(l, r))
    
cache = {}
L = [map(int, raw_input().split()) for _ in xrange(input())]
print dfs(0, len(L) - 1)

Submission status: Accepted

Solution code:
"""
dp[i][j] ... j ~ j + i までまとめた時の最小コスト
dp[0][j] = 0
dp[i][j] = min(dp[k][j] + dp[i - k][j + k + 1] +\
               top[j] * bottom[j + k] * top[j + k + 1] * bottom[j + i] for k in range(i))
"""
INF = 10 ** 20
n = int(input())
top = []
bottom = []
for _ in range(n):
  a, b = map(int, input().split())
  top.append(a)
  bottom.append(b)
dp = [[INF] * (n + 1) for _ in range(n + 1)]
for j in range(n):
  dp[0][j] = 0

for i in range(1, n):
  for j in range(n - i):
    dp[i][j] = min(dp[k][j] + dp[i - k - 1][j + k + 1] +\
                  top[j] * bottom[j + k] * top[j + k + 1] * bottom[j + i] for k in range(i))
print(dp[n - 1][0])

Submission status: Accepted

Solution code:
Card = {}
Cost = {}
n = int(raw_input())
for i in range(n):
  Card[(i, i)] = map(int, raw_input().split())
  Cost[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    Cost[(j, j+i)] = min([reduce(lambda a,b: a*b, Card[(j, j+k)]+Card[(j+k+1, j+i)]) + Cost[(j, j+k)]+Cost[(j+k+1, j+i)] for k in range(i)])
    Card[(j, j+i)] = [Card[(j, j)][0], Card[(j+i, j+i)][1]]
print Cost[0, n-1]

Submission status: Accepted

Solution code:
def f(a,b): return [Card[a][0], Card[b][1]]
n = int(raw_input())
Card = [[] for _ in [0]*n]
Cost = {}
for i in range(n):
  Card[i] = map(int, raw_input().split())
  Cost[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    Cost[(j, j+i)] = min([reduce(lambda a,b: a*b, f(j,j+k)+f(j+k+1,j+i)) + Cost[(j, j+k)]+Cost[(j+k+1, j+i)] for k in range(i)])
print Cost[0, n-1]

Submission status: Accepted

Solution code:
def f(a,b): return [Card[a][0], Card[b][1]]
n = int(raw_input())
Card = [[] for _ in [0]*n]
Cost = {}
for i in range(n):
  Card[i] = map(int, raw_input().split())
  Cost[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    a = j+i
    Cost[(j, a)] = min([reduce(lambda a,b: a*b, f(j, k) + f(k+1, a)) + Cost[(j, k)] + Cost[(k+1, a)] for k in range(j, j+i)])
print Cost[0, n-1]

Submission status: Accepted

Solution code:
n = int(raw_input())
Card = [[] for _ in [0]*n]
Cost = {}
for i in range(n):
  Card[i] = map(int, raw_input().split())
  Cost[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    a = j+i
    Cost[(j, a)] = min([reduce(lambda a,b: a*b, [Card[j][0],Card[k][1],Card[k+1][0],Card[a][1]]) + Cost[(j, k)] + Cost[(k+1, a)] for k in range(j, j+i)])
print Cost[0, n-1]

Submission status: Accepted

Solution code:
n = int(raw_input())
Card = [[] for _ in [0]*n]
Cost = {}
for i in range(n):
  Card[i] = map(int, raw_input().split())
  Cost[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    a = j+i
    Cost[(j, a)] = min([Card[j][0] * Card[k][1] * Card[k+1][0] * Card[a][1] + Cost[(j, k)] + Cost[(k+1, a)] for k in range(j, j+i)])
print Cost[0, n-1]

Submission status: Accepted

Solution code:
n = int(raw_input())
C = [[] for _ in [0]*n]
W = {}
for i in range(n):
  C[i] = map(int, raw_input().split())
  W[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    a = j+i
    W[(j, a)] = min([C[j][0] * C[k][1] * C[k+1][0] * C[a][1] + W[(j, k)] + W[(k+1, a)] for k in range(j, j+i)])
print W[0, n-1]

Submission status: Accepted

Solution code:
n = int(raw_input())
C = [[] for _ in [0]*n]
W = {}
for i in range(n):
  C[i] = map(int, raw_input().split())
  W[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    a = j+i
    W[(j, a)] = min([C[j][0] * C[k][1] * C[k+1][0] * C[a][1] + W[(j, k)] + W[(k+1, a)] for k in range(j, a)])
print W[0, n-1]

Submission status: Accepted

Solution code:
n=int(input())
cards=[]
for i in range(n):
    a,b=map(int,input().split())
    cards.append((a,b))

memo=[[-1 for i in range(n+1)]for j in range(n+1)]
def getans (l,r,cards):
    if(memo[l][r]==-1):
        if(l+1==r):
            memo[l][r]=0
        else:
            ans=1<<32
            for m in range(l+1,r):
                cost=cards[l][0]*cards[m-1][1]*cards[m][0]*cards[r-1][1]+getans(l,m,cards)+getans(m,r,cards)
                ans=min(ans,cost)
            memo[l][r]=ans
    return memo[l][r]

print(getans(0,n,cards))

Submission status: Accepted

Solution code:
n = input()
C = [map(int, raw_input().split()) for i in xrange(n)]
memo = {(i, i): 0 for i in xrange(n)}
def calc(i, j):
    if (i, j) in memo:
        return memo[i, j]
    res = memo[i, j] = min(calc(i, k) + calc(k+1, j) + C[i][0]*C[k][1]*C[k+1][0]*C[j][1] for k in xrange(i, j))
    return res
print calc(0, n-1)

Submission status: Accepted

Solution code:
# AOJ 0145 Cards
# Python3 2018.6.18 bal4u
#　動的計画法　（行列の積に類似）

INF = 0x7fffffff

n = int(input())
c = [[INF for j in range(n)] for i in range(n)]
a = [[0 for j in range(2)] for i in range(n)]

for i in range(n): c[i][i] = 0
for i in range(n): a[i][0], a[i][1] = list(map(int, input().split()))

for l in range(1, n):
	for i in range(n-l):
		j = i + l
		for k in range(i, j):
			c[i][j] = min(c[i][j], c[i][k] +a[i][0]*a[k][1]*a[k+1][0]*a[j][1] +c[k+1][j])

print(c[0][n-1])

Submission status: Accepted

Solution code:
def dfs(l, r):
    if l == r:
        return 0
    if (l, r) in cache:
        return cache[(l, r)]
    cache[(l, r)] = min(dfs(l, m) + dfs(m + 1, r) + L[l][0] * L[m][1] * L[m + 1][0] * L[r][1] for m in xrange(l, r))
    return cache[(l, r)]

cache = {}
L = [map(int, raw_input().split()) for _ in xrange(input())]
print dfs(0, len(L) - 1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

n = int(input())
a = [1] * n
b = [1] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [[INF] * (n + 10) for _ in range(n + 10)]
up = [[1] * (n + 10) for _ in range(n + 10)]
down = [[1] * (n + 10) for _ in range(n + 10)]
for i in range(n):
    dp[i][i] = 0
    up[i][i] = a[i]
    down[i][i] = b[i]
for L in range(n - 2, -1, -1):
    for R in range(L + 1, n):
        dp[L][R] = min(dp[L][i] + dp[i+1][R] + up[L][i] * down[L][i] * up[i + 1][R] * down[i + 1][R] for i in range(L, R))
        for i in range(L, R):
            if dp[L][i] + dp[i+1][R] + up[L][i] * down[L][i] * up[i + 1][R] * down[i + 1][R] == dp[L][R]:
                up[L][R] = up[L][i]
                down[L][R] = down[i + 1][R]
print(dp[0][n - 1])