posts - 74,  comments - 33,  trackbacks - 0

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年12月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜