2011-06-10 20:50:09Morris
d652. 貪婪之糊
http://zerojudge.tw/ShowProblem?problemid=d652
內容 :
發客森林,位於艾克隆城附近的一個充滿毒沼和奇怪生物的森林。
這座森林裡有一種奇妙的生物
叫做「貪婪之糊」,是一群非常greedy的醬糊
貪婪之糊之間喜歡玩一個詭異的遊戲
由於兩隻(陀)貪婪之糊包夾另一個貪婪之糊並且把它吸收掉
現在他們的遊戲規則是這樣的
所有的貪婪之糊成一直線排列
每隻貪婪之糊都有不同的大小
可以選擇連續的三個例如A.B.C
由AC包夾吸收掉B
(雖然說是吸收,但是這不會讓A或C的大小增加…因為它們太貪婪了)
然而這麼做會讓沼澤受到污染,污染值P=A的大小×B的大小×C的大小
最後存活下來沒有被吸收掉的那兩陀貪婪之糊就是贏家
但是聰明的你發現這遊戲根本是個陰謀(太可怕了!)
那就是勝利者永遠是最左邊的和最右邊的貪婪之糊
現在的狀況是你誤闖了發客森林
並且目睹了這個奇妙的遊戲(儀式?)
現在有兩陀貪婪之糊想要串通起來贏得這個遊戲
但是不知道要怎麼樣才能讓遊戲造成的污染最小
(他們雖然很貪婪,可是很愛惜他們住的地方)
於是威脅迷路的你
如果不幫他們兩個寫程式算出來的話…
就要把你吸收掉!XD
這座森林裡有一種奇妙的生物
叫做「貪婪之糊」,是一群非常greedy的醬糊
貪婪之糊之間喜歡玩一個詭異的遊戲
由於兩隻(陀)貪婪之糊包夾另一個貪婪之糊並且把它吸收掉
現在他們的遊戲規則是這樣的
所有的貪婪之糊成一直線排列
每隻貪婪之糊都有不同的大小
可以選擇連續的三個例如A.B.C
由AC包夾吸收掉B
(雖然說是吸收,但是這不會讓A或C的大小增加…因為它們太貪婪了)
然而這麼做會讓沼澤受到污染,污染值P=A的大小×B的大小×C的大小
最後存活下來沒有被吸收掉的那兩陀貪婪之糊就是贏家
但是聰明的你發現這遊戲根本是個陰謀(太可怕了!)
那就是勝利者永遠是最左邊的和最右邊的貪婪之糊
現在的狀況是你誤闖了發客森林
並且目睹了這個奇妙的遊戲(儀式?)
現在有兩陀貪婪之糊想要串通起來贏得這個遊戲
但是不知道要怎麼樣才能讓遊戲造成的污染最小
(他們雖然很貪婪,可是很愛惜他們住的地方)
於是威脅迷路的你
如果不幫他們兩個寫程式算出來的話…
就要把你吸收掉!XD
輸入說明
:
每個測資點僅一筆測資,無須重複讀入
第一行有正整數n(2<n<=50)表示這一列有幾陀貪婪之糊
第二行有n個正整數A(0<A<100),順序表示這n陀貪婪之糊的大小
第一行有正整數n(2<n<=50)表示這一列有幾陀貪婪之糊
第二行有n個正整數A(0<A<100),順序表示這n陀貪婪之糊的大小
輸出說明
:
請輸出最小污染值(答案保證不超過1000000000)
範例輸入 :
//sample1 5 1 2 3 4 5 //sample2 7 12 3 5 11 15 5 4
範例輸出 :
//sample1 38 //sample2 1089
提示
:
出處
:
看成是 (12x3) * (3x5) * (5x11) * (11x15) ...
/**********************************************************************************/
/* Problem: d652 "貪婪之糊" from jack1 */
/* Language: C */
/* Result: AC (2ms, 268KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-06 11:47:43 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, A[50];
while(scanf("%d", &n) == 1) {
int DP[51][51] = {}, a, b, c, d;
for(a = 0; a < n; a++)
scanf("%d", &A[a]);
for(a = 1, n--; a < n; a++) {
for(b= 0, c= a + b; c < n; b++, c++) {
int min = 2147483647, t;
for(d = b; d < c; d++) {
t = DP[b][d] + DP[d+1][c] + A[b]*A[d+1]*A[c+1];
min = (min < t) ? min : t;
}
DP[b][c] = min;
}
}
printf("%d\n", DP[0][n-1]);
}
return 0;
}
上一篇:d646. I2A的陰謀
下一篇:a144. 整數分拆