7.3 The Mystic Crystal Garden
Saee is exploring a mystical crystal garden shaped like a perfect convex n-sided enclosure.
Each corner of the garden holds a crystal orb, each glowing with a special integer energy value.
The energy values of the orbs are given in clockwise order in an array called values, where values[i] represents the energy at the i-th orb.
To unlock the Heart of the Garden, Saee must connect these orbs with invisible energy beams such that the enclosure is divided into triangular zones.
Each triangle must use only the original orbs as its vertices, and no overlapping or extra shapes are allowed.
After this process, there will be exactly n - 2 triangles.
Every triangle has an energy weight, calculated as the product of the three orb values at its vertices.
The total energy cost of Saee’s configuration is the sum of all triangle weights formed.
Saee’s goal is to find the minimum possible total energy cost she can achieve by choosing the best way to divide the enclosure.
Constraints
1 ≤ t ≤ 100
3 ≤ n ≤ 50
1 ≤ values[i] ≤ 100
Input Format
Each test contains multiple test cases.
The first line contains an integer t — the number of test cases (1 ≤ t ≤ 100).
The description of each test case follows.
- The first line of each test case contains an integer n (3 ≤ n ≤ 50) — the number of crystal orbs.
- The second line contains n integers values[i] (1 ≤ values[i] ≤ 100) — representing the energy values of each orb in clockwise order.
Output Format
For each test case, output a single integer — the minimum total energy cost required to unlock the Heart of the Garden.
Example 1
Input:
3
3
1 2 3
4
3 7 4 5
6
1 3 1 4 1 5
Output:
6
144
13
Explanation:
Test Case 1:
Only one triangle is possible. Its energy cost is 1 × 2 × 3 = 6.
Test Case 2:
Two triangulations are possible:
(3×7×5) + (4×5×7) = 245
(3×4×5) + (3×4×7) = 144
The second one gives the minimum energy cost 144.
Test Case 3:
Saee’s optimal configuration yields a total energy cost of 13.
Log In to solve the Question