for
(k
=
1
;k
<
n;k
++
)
????????????
for
(i
=
1
;i
<=
n
-
k;i
++
)
????????????????
for
(j
=
i;j
<
i
+
k;j
++
)
{
????????????????????Mdp[i][i
+
k]
=
getmax(Mdp[i][i
+
k],Sum(Mdp[i][j],flag[j],Mdp[j
+
1
][i
+
k]));
????????????????????Mdp[i][i
+
k]
=
getmax(Mdp[i][i
+
k],Sum(mdp[i][j],flag[j],mdp[j
+
1
][i
+
k]));
????????????????????mdp[i][i
+
k]
=
getmin(mdp[i][i
+
k],Sum(Mdp[i][j],flag[j],Mdp[j
+
1
][i
+
k]));
????????????????????mdp[i][i
+
k]
=
getmin(mdp[i][i
+
k],Sum(mdp[i][j],flag[j],mdp[j
+
1
][i
+
k]));
????????????????}
????????????????
5019 Max
TimeLimit : 1 Second ? Memorylimit : 32 Megabyte ?
Totalsubmit : 114 ? Accepted : 28
Give you a expression,you can add some parenthesis to maximize result.Example as following:
1 + 2 * 3
Its result is 7 in the example.But you can add a parenthesis like (1 + 2) * 3,then the result is 9,and so it is the maximization of the example.You job is to find the maximizaton of a expression. To simplify this problem,you can assume that expression contains only operator + and *,but note that integers may be negative.
Input
Input contains multiple test cases.Each case begin with a integer N(2<=N<=100), the number of integers of a expression.Then follows the expression.Integers and operator spearate with a single whitespace.
Output
For each case print a single line with the maximized value of the expression.
Sample Input
4
1 + 2 * 3 + -1
Sample Output
8
這題應該算是經典dp里面的題目。
至于方法同棋盤分割，三角刨分，大體相同。
主要是處理的時候要打兩張表，最大最小的表
部分代碼如下
posted on 2009-02-20 14:13
KNIGHT 閱讀(103)
評論(0) 編輯 收藏 引用