S93-CA2-2
Time Limit: 1 Second Memory Limit: 65536 KB
E.Nigma
رابین در
پارک مشغول جستجو بود که ناگهان در یکی از تله‌های ریدلر افتاد. ریدلر از این که
شخص بتمن به دام وی نیفتاده ناراحت بود، به همین خاطر تصمیم گرفت سوال پیچیده‌ای
به رابین بدهد تا نتواند آن را حل کند. معما به صورت زیر است:
تعدادی (n) کارت در یک ردیف داریم. هر کدام از این کارت‌ها یک شماره دارند،
می‌خواهیم کارت‌ها را به ترتیبی از این ردیف برداریم. هر کارتی که بر می‌داریم
امتیاز عدد آن کارت ضربدر عدد کارت سمت چپ ضربدر عدد کارت سمت راست آن کارت را
از دست می‌دهیم. هم‌چنین نمی‌توانیم کارت‌های ابتدا و انتها‌ی ردیف را برداریم. آن‌قدر
کارت برمی‌داریم تا تنها ۲ کارت ابتدا و انتهایی باقی بماند. برای نمونه‌ی محاسبه‌ی
امتیاز از دست رفته فرض کنید ۵ کارت با اعداد 5 , 6 , 10, 25, 1 داریم.
|
ترتیب انتخاب کارت |
امتیازی که از دست می‌دهیم |
|
6, 10, 25 |
5*6*10 + 5*10*25 + 5*25*1 = 1675 |
|
25, 10, 6 |
10*25*1 + 6*10*1 + 5*6*1 = 340 |
ریدلر تعدادی کارت جلوی رابین می‌گذارد و از
او می‌خواهد تا ترتیبی انتخاب کند که کمترین امتیاز را از دست بدهد. رابین که نمی‌تواند
این مساله را حل کند از اوراکل کمک می‌خواهد تا جوابی پیدا کند. برای اوراکل برنامه‌ای
بنویسید که ترتیبی پیدا کند تا مجموع امتیازی که رابین از دست می‌دهد کمینه شود.
Input
Output
برای
هر مورد، کمینه‌ی امتیازی که از دست می‌رود را بنویسید.
Sample Input
2 5 5 6 10 25 1 6 10 1 50 50 20 5
Sample Output
340 3650Submit