Once at atcoder I've got the problem which listed bellow. I suppose that it's a DP problem. But I'm not quite sure...

short description. We have vector of ints as input. We should order elements in a way to maximise total sum of adjacent products. max sum = a1*a2 + a2*a3 + ... + an-1*an some of numbers have fixed positions , so you can't move them.

Initially I was thinking that the best way will be to sort sequence in decreasing order and start constructing binary tree and adding gradually new elements to the ones that give max local product. input = 10 40 30 50 50 / \ 30 40 but this idea is not sufficient for solving the problem.

Can you please give me some hint how to approach a problem? Thanks in advance!

Original problem D — 積の総和/SumTotal of product Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Question There are N empty cells in a grid that are aligned horizontally in one line and N numbers A1, A2, …, AN.

The goal is to organize the integers in A1, A2, …, AN to maximize S, where S represents of the sum of the products of all adjacent pairs of numbers.

Some cells may have already been assigned an integer value and cannot be changed.

Your program should output the maximum value of S.

When representing the index for the number that is assigned to the i(1≦i≦N)th cell from the left as Ii, S could be represented as: S=AI1×AI2+AI2×AI3+…++AIN−1×AIN.

Input The input will be given in the following format on Standard Input

N
A1 D1
A2 D2
:
AN D3

On the 1st line, integer N(1≦N≦16) is given. From 2nd line to Nth line, information regarding each number is given. The ith line contains the value of the ith integer Ai(−100≦Ai≦100) and an integer Di(1≦Di≦N or Di=−1). If Ai has not yet been assigned a cell, Di=−1. Otherwise, the Di represents the cell to which the integer has been assigned. Specifically, when Di≦0, it indicates that Ai is assigned to Dith cell from the left. Multiple numbers will not be assigned to the same cell. Output On the 1st line, the maximum value of S should be output.

Ensure that there is a line break following S.

Input Example #1
5
10 -1
20 -1
50 -1
40 -1
30 -1
Output1 Example 1#
4600

For example, if assigning each cell 10, 30, 50, 40, 20 from the left, it becomes 10×30+30×50+50×40+40×20=4600, which is the maximum value one can achieve

Input Example #2
6
10 3
20 -1
50 -1
40 -1
30 -1
60 6
Output Example #2
6300

In this case, it is already decided that the 3rd cell from the left will be assigned the number 10 and the 6th cell from the left the number 60.

In this case, if assigning each cell 20, 30, 10, 40, 50, 60 from the left, the maximum value 6300 will be achieved.

Input Example #3
2
100 -1
0 -1
Output Example #3
0

Input Example #4
16
1 -1
-2 -1
3 -1
-4 -1
5 -1
-6 -1
7 -1
-8 -1
9 -1
10 -1
11 -1
12 -1
13 -1
14 -1
15 -1
-16 -1
Output Example #4
1342

Input Example #5
16
-8 -1
0 -1
0 11
8 -1
-10 -1
7 -1
-2 -1
-7 -1
0 -1
-4 -1
-4 8
-10 -1
-4 1
0 -1
-8 -1
6 -1
Output Example #5
504