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

輸入說明 :

每個測資點僅一筆測資,無須重複讀入
第一行有正整數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

提示 :

出處 :

jack1 (管理:jack1)

作法 : DP
最小矩陣乘積鏈
12 3 5 11 15 5 4
看成是 (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. 整數分拆