多边形游戏

多边形游戏多边形信息•单人玩游戏•开始时有一个由n个顶点构成的多边形•所有边和顶点依次用整数从1到n编号•每个顶点被赋予一个整数值•每条边被赋予一个运算符“+”或“×”首先删除一条边游戏规则随后n-1步按以下方式操作：E2V1V1、选择连接着2个顶点和的边1V2VE2、2个顶点和通过边上的运算符计算得到结果赋予新的顶点12,opVV12,opVV1V2V运算后得到新顶点•最后所有边都被删除，游戏结束，所剩顶点上的整数值就是游戏的得分•问题:对于给定的多边形，计算最高得分。从顶点开始，长度为(链中有个顶点)的顺时针链可表示为如果这条链的最后一次合并运算在处发生，则可在处将链分割为2个子链和。最优子结构性质1ini()pij，1[1],1viopiopijvij，，，jj[]opis11sj[]opis()pis，()pisjs，iV1ijV()pij，[]opis+1isV+isViV+1isV+isV+1ijV1amb2cmd()pis，()pisjs，子链，任意一种合并方式得到的值，分别为最大值和最小值同理子链，任意一种合并方式得到的值，分别为最大最小值1m,ab2m,cd12(,)()([])pijmmopism主链的值最优子结构性质•(1)当时，显然有•(2)当时，有•主链的最大值和最小值•可由子链的最大值和最小值得到。''[]opisacmbd''[]opis{}{}minacadbcbdmmaxacadbcbd，，，，，，•由上述分析可知欲求主链的最大值，必须同时计算子链的最大值和最小值，所以设链的最大值最小值于是有递归求解,,0mij,,1mij(,)pij,,0amiis,,0cmisjs,,1bmiis,,1dmisjs•(1)当时(2)当时，''[]opis''[]opis,,0=miisac,,1=miisbd,,0={}minacadmiisbcbd，，，,,1={}maxacadmiisbcbd，，，•综合得到•主链在处断开最大值最小值•由于断开的位置s有j-1中情况，可得(,)pij[]opis[]min(,,){,,,}['''']acfijsminaopisopcadbicsbd[]max(,,){,,,}['''']bdfijsmaxaopisopcadbicsbd11sj,,0=min(,,)1,,,1=max(,,)isjisjmiisfijsijnmiisfijs•初始的边界值为•由于多边形是封闭的，所以当时，顶点的编号为所以按上式递推即为游戏首次删去第i条边得到的最大分数,1,0=[]1,1,1=[]miviinmivi+isn+is(+)modisn,,1min