{"id":"a0a88379-de4c-4918-9b25-5cc1b4e0e6de","name":"Minimum Score Of Triangulation","description":"1. You are given an array of integers, which represents the vertices of an N-sided convex polygon in clockwise order.\r\n2. You have to triangulate the given polygon into N-2 triangles.\r\n3. The value of a triangle is the product of the labels of vertices of that triangle.\r\n4. The total score of the triangulation is the sum of the value of all the triangles.\r\n5. You have to find the minimum score of the triangulation of the given polygon.","inputFormat":"A number N\r\na1\r\na2.. N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 1000\r\n1 &lt;= arr[i] &lt;= 100","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static int minScoreTriangulation(int[] arr) {\r\n\t\t//write your code here\r\n\t\t\r\n\t\treturn 0;\r\n }\r\n public static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n\t\tfor(int i = 0 ; i < n; i++){\r\n arr[i] = scn.nextInt();\r\n }\r\n System.out.println(minScoreTriangulation(arr));\r\n\t}\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3\r\n1\r\n2\r\n3","sampleOutput":"6\r\n","questionVideo":"https://www.youtube.com/embed/tmIhmeL8WRo?end=158","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"915f1a45-7cfb-4521-a532-9e2a75c86bca","name":"Minimum Score Of Triangulation","slug":"minimum-score-of-triangulation","type":1}],"next":{"id":"2e9f4330-5c9f-461e-8fb1-410b2357d781","name":"MINIMUM SCORE OF TRIANGULATION MCQ","type":0,"slug":"minimum-score-of-triangulation-mcq"},"prev":{"id":"50c0b4ed-e31c-4bce-873e-32b71451fad8","name":"Burst Balloons","type":3,"slug":"burst-balloons"}}}

Minimum Score Of Triangulation

1. You are given an array of integers, which represents the vertices of an N-sided convex polygon in clockwise order. 2. You have to triangulate the given polygon into N-2 triangles. 3. The value of a triangle is the product of the labels of vertices of that triangle. 4. The total score of the triangulation is the sum of the value of all the triangles. 5. You have to find the minimum score of the triangulation of the given polygon.

{"id":"a0a88379-de4c-4918-9b25-5cc1b4e0e6de","name":"Minimum Score Of Triangulation","description":"1. You are given an array of integers, which represents the vertices of an N-sided convex polygon in clockwise order.\r\n2. You have to triangulate the given polygon into N-2 triangles.\r\n3. The value of a triangle is the product of the labels of vertices of that triangle.\r\n4. The total score of the triangulation is the sum of the value of all the triangles.\r\n5. You have to find the minimum score of the triangulation of the given polygon.","inputFormat":"A number N\r\na1\r\na2.. N integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 1000\r\n1 &lt;= arr[i] &lt;= 100","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static int minScoreTriangulation(int[] arr) {\r\n\t\t//write your code here\r\n\t\t\r\n\t\treturn 0;\r\n }\r\n public static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n\t\tfor(int i = 0 ; i < n; i++){\r\n arr[i] = scn.nextInt();\r\n }\r\n System.out.println(minScoreTriangulation(arr));\r\n\t}\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3\r\n1\r\n2\r\n3","sampleOutput":"6\r\n","questionVideo":"https://www.youtube.com/embed/tmIhmeL8WRo?end=158","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"915f1a45-7cfb-4521-a532-9e2a75c86bca","name":"Minimum Score Of Triangulation","slug":"minimum-score-of-triangulation","type":1}],"next":{"id":"2e9f4330-5c9f-461e-8fb1-410b2357d781","name":"MINIMUM SCORE OF TRIANGULATION MCQ","type":0,"slug":"minimum-score-of-triangulation-mcq"},"prev":{"id":"50c0b4ed-e31c-4bce-873e-32b71451fad8","name":"Burst Balloons","type":3,"slug":"burst-balloons"}}}
plane

Editor

Loading...

Minimum Score Of Triangulation

medium

1. You are given an array of integers, which represents the vertices of an N-sided convex polygon in clockwise order. 2. You have to triangulate the given polygon into N-2 triangles. 3. The value of a triangle is the product of the labels of vertices of that triangle. 4. The total score of the triangulation is the sum of the value of all the triangles. 5. You have to find the minimum score of the triangulation of the given polygon.

Constraints

1 <= N <= 1000 1 <= arr[i] <= 100

Format

Input

A number N a1 a2.. N integers

Output

Check the sample output and question video.

Example

Sample Input

3 1 2 3

Sample Output

6

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode