2011-06-18 08:19:59Morris
b061. 6. 糊塗情報員
http://zerojudge.tw/ShowProblem?problemid=b061
內容 ：
有一位間諜，依他所屬情報單位要求編碼方式，將他所收集到情報全部編成數字碼。但他認為這樣還是不夠安全，因此他再將這些數字字串，隨意切割成好幾個整
數，然後將每個整數用一個數學算式來表示。這些算式只用了加、減、乘三種運算子，而且每個運算元都是正整數。最後，他為了讓他自己更為心安，他將整個密碼
分成兩本密碼簿儲存。密碼本A存放這些數學算式，但他將算式內的所有括號全部拿掉，然後再將這些拿掉的括號資訊記錄在密碼本B裡面。
過了不久他返 國述職，發現他把密碼本B弄丟了。再加上他的記憶力不好，很多情報內容根本記不得，所以現在沒了密碼本B幾乎束手無策。在不得已的情況下他的情報單位派了 幾位心理與腦神經生理專家詢問他，希望能喚起他腦海內的記憶。這些專家試了好幾天，用盡各種心理生理辦法後，終於承認他的記憶力果真很差，怎麼也問不出情 報內容。倒是心理學專家有一發現，即這位情報員在寫密碼算式時，傾向於將括號加在那些會讓算式得最大值的位置。例如5*7+2這個算式，有兩種括法： ((5*7)+2)以及(5*(7+2))，第二種括法所得的值較大。請寫一程式，算出這些算式的可能最大值。
過了不久他返 國述職，發現他把密碼本B弄丟了。再加上他的記憶力不好，很多情報內容根本記不得，所以現在沒了密碼本B幾乎束手無策。在不得已的情況下他的情報單位派了 幾位心理與腦神經生理專家詢問他，希望能喚起他腦海內的記憶。這些專家試了好幾天，用盡各種心理生理辦法後，終於承認他的記憶力果真很差，怎麼也問不出情 報內容。倒是心理學專家有一發現，即這位情報員在寫密碼算式時，傾向於將括號加在那些會讓算式得最大值的位置。例如5*7+2這個算式，有兩種括法： ((5*7)+2)以及(5*(7+2))，第二種括法所得的值較大。請寫一程式，算出這些算式的可能最大值。
輸入說明
：
每一筆輸入資料為一行算式，運算子只有三種即一般的加、減、乘三種二元運算子，分別以符號 "+"、"-"、"*" 表示。
每一個運算元都是一個正整數( ≤ 100)，運算元和運算子之間不會有空白，一行算式不會有超過50個運算元。
每一個運算元都是一個正整數( ≤ 100)，運算元和運算子之間不會有空白，一行算式不會有超過50個運算元。
輸出說明
：
相對於每一輸入算式，輸出所有可能運算結果的最大值。該值都會是一個正整數，而且不會超過2147483647。
範例輸入 ：
5*7+2 6*3-9*3 5+2-7*2-3
範例輸出 ：
45 27 14
提示
：
出處
：
95全國資訊學科能力決賽
作法 : DP
更新方法與矩陣乘積鏈相同，不過要同時紀錄min & max
因為 min*min 可能成為max，max * min 可以成為 min
例子：
5+2-7*2-3
［5+2］=7，［2-7］=-5，［7*2］=14，［2-3］=-1
［5+2-7］= ［(5+2)-7］= ［5+(2-7)］
［2-7*2］= ［(2-7)*2］= ［2-(7*2)］
［7*2-3］= ［(7*2)-3］= ［7*(2-3)］
［5+2-7*2］=［(5+2)-(7*2)］= ［(5+2-7)*2］= ［5+(2-7*2)］...
/**********************************************************************************/
/* Problem: b061 "6. 糊塗情報員" from 95全國資訊學科能力決賽 */作法 : DP
更新方法與矩陣乘積鏈相同，不過要同時紀錄min & max
因為 min*min 可能成為max，max * min 可以成為 min
例子：
5+2-7*2-3
［5+2］=7，［2-7］=-5，［7*2］=14，［2-3］=-1
［5+2-7］= ［(5+2)-7］= ［5+(2-7)］
［2-7*2］= ［(2-7)*2］= ［2-(7*2)］
［7*2-3］= ［(7*2)-3］= ［7*(2-3)］
［5+2-7*2］=［(5+2)-(7*2)］= ［(5+2-7)*2］= ［5+(2-7*2)］...
/**********************************************************************************/
/* Language: C */
/* Result: AC (4ms, 276KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-17 20:01:13 */
/**********************************************************************************/
#include<stdio.h>
#define Maxv 2147483647
#define Minv -2147483647
int opera[52], num[52];
int Calc(int x, int op, int y) {
switch(op) {
case '+':return x+y;
case '-':return x-y;
case '*':return x*y;
}
}
int Min(int x, int y) {
if(x < y) return x;
return y;
}
int Max(int x, int y) {
if(x > y) return x;
return y;
}
int DP(int n) {
int a, b, c, d, min, max;
int t1, t2, t3, t4;
int DPmin[52][52], DPmax[52][52];
for(a = 0; a < n; a++)
DPmin[a][a] = DPmax[a][a] = num[a];
for(a = 1; a < n; a++)
for(b= 0, c= a + b; c < n; b++, c++) {
min = Maxv, max = Minv;
for(d = b; d < c; d++) {
t1 = Calc(DPmin[b][d], opera[d], DPmin[d+1][c]);
t2 = Calc(DPmin[b][d], opera[d], DPmax[d+1][c]);
t3 = Calc(DPmax[b][d], opera[d], DPmax[d+1][c]);
t4 = Calc(DPmax[b][d], opera[d], DPmin[d+1][c]);
min = Min(Min(Min(t1, t2), Min(t3, t4)), min);
max = Max(Max(Max(t1, t2), Max(t3, t4)), max);
}
DPmin[b][c] = min;
DPmax[b][c] = max;
}
return DPmax[0][n-1];
}
main() {
char s[1001];
while(scanf("%s", s) == 1) {
int a, ot = 0, nt = 0, t =0;
for(a = 0; s[a]; a++) {/*analysis*/
if(s[a] >= '0' && s[a] <= '9')
t = t*10 + s[a]-'0';
else {
num[nt++] = t;
opera[ot++] = s[a];
t = 0;
}
}
num[nt++] = t;
printf("%d\n", DP(nt));
}
return 0;
}