《[计算机]《糊涂情报员》解题报告》由会员分享，可在线阅读，更多相关《[计算机]《糊涂情报员》解题报告（5页珍藏版）》请在金锄头文库上搜索。
1、第一轮省选解题报告By sx349 【摘要】核心算法思想：动态规划主要数据结构：其他辅助知识：数论时间复杂度： （N 为式子中的数的个数）3()O空间复杂度： 2【题目大意】给定一个式子，给这个式子增加括号，使这个式子的值最大。【算法分析】根据给定的式子添加括号的过程，实质上是改变式子中每一个运算符的先后运算顺序。显然，式子运算的最后一步必然是选择该式子中的某个运算符，并且将运算符前后的式子的值进行运算。而我们的目的就是求得最后整个式子的最大值。考虑将整个式子中的每一个数即为一个节点，显然，我们可以直接得到一个朴素的算法：枚举每一步的操作，得到最终结果。显然，其时间复杂度将达到 ，这显然是不能
2、接(!)ON受的。但是我们由此考虑开去，经过这每一步的操作，我们其实建立了一棵运算树，树的每一个叶子结点是一个数字，每个非叶子节点是一个运算符，且必然连接左右两个子节点，而这棵树的后序遍历就是我们最初的式子。显然，假设我们建立了树的一部分，那么树的其他部分对这一部分的值是没有任何影响的，这样，我们可以考虑分部分解决这个问题。根据这个思路，可以得到如下的一个算法。我们先考虑从第 I 个数字开始，第 J 个数字结束的一段式子的最大值，显然，我们可以得到如下的状态转移方程： 1,max(,)jkfiworijk其中，函数 计算的是从 i 到 j 并在 k 处中断时得到的最大值。考虑在 k 处运算符不
3、同的情况下 的求法：(,)or若运算符为+ ，则 ,1,wkijfikfj若运算符为- ，则 (),r若运算符为* ，则(,)max,*1,*1,*1,*1,workijfikfjfikfjfikfjfikfj其中用到了另一个状态 ，表示从第 I 个数字开始，第 J 个数字结束的一段式子的最j小值。考虑最小值的原因主要是中间过程可能有负数出现，可能某一步中的最大值是由两个最小的负数相乘得到的，或者是由运算符左侧得数的最大值减去运算符右侧得数的最小值得到的。因此如果不考虑最小值，就会导致最大值出现偏差。因此，我们还要考虑 的值：,fij1,min(,)jkfiwork并且考虑 的求法：j若运算符
4、为+ ，则 (,),1,rkijfikfj若运算符为- ，则 wo若运算符为* ，则(,)min,*1,*1,*1,*1,workijfkfjfikfjfikfjfikfj计算出 和 中的值后，输出 （n 为数字总数） 。fj显然，在计算时我们需要先计算 的情况，然后是 ，依次递增。这样，访0jiji问的时候基本上是跳跃式的。因此，我们把 表示为从第 I 个数字开始，数字长度为,fijJ 的一段式子的最大值，这样在计算时，就可以在访问时连续访问相近的格子，减少了跳跃式访问造成的寻址时间。【心得体会】这次省选的题目当中也许这是最简单的一道，但这道题也相对比较考察选手的细心程度。题目的样例选择了一
5、个会有最小数影响结果的式子，我在一开始考虑时也并没有考虑一段式子的最小值，在带入样例时才发现了这一点。诚然，也许这样做是出题者有所考虑的缘故，但是，如果当初恰好选择了一个不受最小值影响的样例，相信像我一样的选手会有很多就因此栽跟头。因此，回顾本题，我更多地看到了自己在细节方面还是欠考虑的。尽管不能将方方面面全部考虑周全，但是在以后的学习中，绝对是需要督促自己考虑的更加周密的。【附录】糊涂情报员【问题描述】有一位间谍，根据他所在情报机构提供的编码方式，将他收集到的情报编成数字码保存，以便有机会时带回国。但他认为这样还不够安全，所以他再将这些数字串随意切割成若干个数字，然后将每个整数用一个数学算式
6、来表示。这些算式只用了加、减、乘三个运算符，且每个运算数均为正整数。最后，他为了让自己更为心安，将整个密码分成两本密码本储存。密码本 A 存放这些数学算式，但他将算式中的所有括号全部拿掉，然后再将这些拿掉的括号资料记录在密码本 B 里。过了不久他有机会回国述职，却不幸遇到车祸头脑受到了损伤，同时密码本 B 也丢掉了。由于头脑受到损伤，他对很多情报的内容已记不太清楚，再加上没有了密码本 B 他几乎是束手无策。在此情况下，该国的情报机关只好动用几位心理专家对他进行记忆唤醒。然而，这些专家在经过各种努力后均无功而返 , 唯一在对他进行深度催眠时发现：这位情报员在写密码算式时，倾向于将括号加在那些会让
7、算式得到最大值的位置。例如： 5*7+2 这个算式，有两种加括号的方法：（5*7）+2）及 (5*(7+2), 显然第二种方法所得到的值较大。果然，经使用此种方法，即算出算式的可能最大值，可将密码破解。现在请你将密码本 A 存放的数学算式算出可能的最大值。【输入】每一数学算式为一行，只用加、减、乘三个运算符 , 每一个运算数都是一个正整数（ 100 ） , 运算符与运算数之间不会有空白。同时，一行运算式不会超过 50 个运算符。【输出】相对于每一个输入的算式，输出运算结果的最大值。该值都会是一个正整数，且不超过 2147483647.【样例】 输入： 6*3-9*3 输出： 27 输入： 5+
8、2-7*2-3 输出： 14【源代码清单】 PROG: ProvinceOI2009LANG: PASCALID: xyj-flashProgram Pro2009_4;ConstMaxN=100;VarNumber:Array1.MaxN of Longint;Opt:Array1.MaxN of Char;F,F2:Array1.MaxN,1.MaxN of Longint;Top,Len,I,J,K,Num,Code:Longint;Str:String;Function Max(A,B:Longint):Longint;BeginIf AB Then Exit(A);Exit(B);
9、End;Function Min(A,B:Longint):Longint;BeginIf AB Then Exit(A);Exit(B);End;Function Work(I,J,K:Longint):Longint;BeginCase OptI+K-1 of+:Work:=FI,K+FI+K,J-K;-:Work:=FI,K-F2I+K,J-K;*:BeginWork:=FI,K*FI+K,J-K;Work:=Max(Work,FI,K*F2I+K,J-K);Work:=Max(Work,F2I,K*FI+K,J-K);Work:=Max(Work,F2I,K*F2I+K,J-K);En
10、d;End;End;Function Work2(I,J,K:Longint):Longint;BeginCase OptI+K-1 of+:Work2:=F2I,K+F2I+K,J-K;-:Work2:=F2I,K-FI+K,J-K;*:BeginWork2:=F2I,K*F2I+K,J-K;Work2:=Min(Work2,FI,K*FI+K,J-K);Work2:=Min(Work2,F2I,K*FI+K,J-K);Work2:=Min(Work2,FI,K*F2I+K,J-K);End;End;End;BeginReadln(Str);Top:=0;If Str1=- Then Str
11、:=0+Str;Len:=Length(Str);I:=1;While I=Len do BeginIf StrI in 0.9 Then BeginJ:=I; While (StrJ in 0.9) and (J=Len) do Inc(J);Val(Copy(Str,I,J-I),Num,Code);Inc(Top);NumberTop:=Num;If J=Len Then OptTop:=StrJ;I:=J+1;End;End;For I:=1 to Top doFor J:=1 to Top do BeginF2I,J:=MaxLongint;FI,J:=-MaxLongint;End;For I:=1 to Top do BeginFI,1:=NumberI;F2I,1:=NumberI;End;For I:=Top-1 downto 1 doFor J:=2 to Top-I+1 doFor K:=1 to J-1 do BeginFI,J:=Max(FI,J,Work(I,J,K);F2I,J:=Min(F2I,J,Work2(I,J,K);End;Writeln(F1,Top);End.
