[ZJ][dp] a578. 苦哈哈機器人工廠
內容 ：
笑嘻嘻機器人工廠是個專門生產機器人的工廠
他們一共出產三種機器人，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
提示
：
出處
：
這題用迭代的方式並不是很好撰寫，用記憶化搜索的方式寫比較方便。
這題的輸入變數真是坑啊。
/**********************************************************************************/
/* 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;
}