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 阅读(83)
评论(0) 编辑 收藏 引用