[ZJ][dp] a578. 苦哈哈機器人工廠＠Morris' Blog

2012-11-22 08:27:19| 人氣243| 回應0 | 上一篇 | 下一篇

[ZJ][dp] a578. 苦哈哈機器人工廠

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

笑嘻嘻機器人工廠是個專門生產機器人的工廠

他們一共出產三種機器人，A機器人、B機器人和C機器人

不只如此，每種機器人還可以依顧客的需要製成各種不同的大小

因為他們實在太厲害了，所以笑嘻嘻機器人工廠裡的人都笑嘻嘻的

沒想到，隨著經濟越來越不景氣

大家填飽肚子都有困難了，越來越少人跟笑嘻嘻工廠買機器人

所以笑嘻嘻工廠就變成了苦哈哈工廠

苦哈哈工廠的老闆為了改善現狀，決定要嚴格控管製作機器人的成本

使機器人製作的成本是最低的

現在已知道大小為n的A機器人可以選擇用下列三個方案其中一個製成：

* a台大小為n-2的B機器人，b台大小為n-1的C機器人，並花費c元的製作費

* d台大小為n-1的C機器人，並花費e元的製作費

* f台大小為n-1的A機器人，並花費g元的製作費

大小為n的B機器人可以選擇用下列三個方案其中一個製成：

* h台大小為n-2的C機器人，i台大小為n-1的A機器人，並花費j元的製作費

* k台大小為n-1的C機器人，並花費l元的製作費

* m台大小為n-2的A機器人，並花費o元的製作費

大小為n的C機器人可以選擇用下列三個方案其中一個製成：

* p台大小為n-3的A機器人，q台大小為n-1的B機器人，並花費r元的製作費

* s台大小為n-1的B機器人，並花費t元的製作費

* u台大小為n-2的C機器人，並花費v元的製作費

另外，機器人的大小最小為1

而大小為1的A機器人的製作費為x元、大小為1的B機器人的製作費為y元、大小為1的C機器人的製作費為z元

請你幫苦哈哈老闆算算看，大小為n的三台機器人的最低成本分別是多少錢，讓他變回笑嘻嘻老闆

輸入說明：

本題為重覆輸入，每筆測資一行，含25個以空白隔開的非負整數，每個數字皆不超過10

分別為本題內容所述之a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,x,y,z

輸出說明：

對每筆測資輸出一行，含三個整數

分別為大小為n的A機器人、B機器人、C機器人的最低製作成本

範例輸入：

1 2 3 1 2 3 1 2 3 1 2 3 1 7 2 3 1 2 3 1 2 3 1 2 3

範例輸出：

21 12 40

提示：

出處：

(管理：VacationClub)

這題用迭代的方式並不是很好撰寫，用記憶化搜索的方式寫比較方便。
這題的輸入變數真是坑啊。

/**********************************************************************************/
/* Problem: a578 "苦哈哈機器人工廠" from                                 */
/* Language: CPP (1644 Bytes)                                                    */
/* Result: AC(4ms, 252KB) judge by this@ZeroJudge                                */
/* Author: morris1028 at 2012-11-20 17:01:18                                     */
/**********************************************************************************/

#include <stdio.h>
#include <string.h>
int a, b, c, d, e;
int f, g, h, i, j;
int k, l, m, n, o;
int p, q, r, s, t;
int u, v, x, y, z;
int A[20], B[20], C[20];
int mmin(int x, int y) {
    if(x == 0) return y;
    return x < y ? x : y;
}
int dpA(int);
int dpB(int);
int dpC(int);
int dpA(int size) {
    if(A[size])
        return A[size];
    if(size > 2)
        A[size] = mmin(A[size], dpB(size-2)*a+dpC(size-1)*b+c);
    A[size] = mmin(A[size], dpC(size-1)*d+e);
    A[size] = mmin(A[size], dpA(size-1)*f+g);
    return A[size];
}
int dpB(int size) {
    if(B[size])
        return B[size];
    if(size > 2)
        B[size] = mmin(B[size], dpC(size-2)*h+dpA(size-1)*i+j);
    B[size] = mmin(B[size], dpC(size-1)*k+l);
    if(size > 2)
        B[size] = mmin(B[size], dpA(size-2)*m+o);
    return B[size];
}
int dpC(int size) {
    if(C[size])
        return C[size];
    if(size > 3)
        C[size] = mmin(C[size], dpA(size-3)*p+dpB(size-1)*q+r);
    C[size] = mmin(C[size], dpB(size-1)*s+t);
    if(size > 2)
        C[size] = mmin(C[size], dpC(size-2)*u+v);
    return C[size];
}
int main() {
    while(scanf("%d %d %d %d %d", &a, &b, &c, &d, &e) == 5) {
        scanf("%d %d %d %d %d", &f, &g, &h, &i, &j);
        scanf("%d %d %d %d %d", &k, &l, &m, &n, &o);
        scanf("%d %d %d %d %d", &p, &q, &r, &s, &t);
        scanf("%d %d %d %d %d", &u, &v, &x, &y, &z);
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(C, 0, sizeof(C));
        A[1] = x, B[1] = y, C[1] = z;
        printf("%d %d %d\n", dpA(n), dpB(n), dpC(n));
    }
    return 0;
}

我要檢舉

#a578#苦哈哈機器人工廠

台長： Morris

您可能對以下文章有興趣

d828. Pascal's triangle's secret (II)

[ZJ][2DST][zkw] d800. ST版区间MAX

d807. 方方

[ZJ][單調堆] a813 2013高雄市能力競賽高中組 4. 城市觀測

人氣(243) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][dp] a491. 貨物集中問題
此分類上一篇:[ZJ][規律] a568. ISSC 2012- problem B

回應(0)