C++动态规划
2010-11-16 13:05:18 来源：WEB开发网核心提示：实例四、多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形，C++动态规划(8)，每个顶点被赋予一个整数值，每条边被赋予一个运算符”+”或”*”，主链的最大值和最小值可由子链的最大值和最小值得到，实现：/* 主题：多边形游戏* 作者：chinazh
实例四、多边形游戏
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符”+”或”*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。
随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题: 对于给定的多边形，计算最高得分。
最优子结构性质
按照顺时针顺序，多边形和顶点的顺序可以写成：
op[1], v[1], op[2], v[2], …, op[n], v[n]
在所给多边形中，从顶点i(1 <= i <= n)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为
v[i], op[i+1], v[i+1],…, op[i+j-1], v[i+j-1]
如果这条链在op[i + s]处进行最后一次合并运算(1 <= s <= j-1)，则可在op[i+s]处将链分割为2个子链：
从i开始长度为s的链： p(i，s)
从i + s开始，长度为j - s的链：p(i + s，j-s)。
设:
m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。
m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。
依此定义有a <= m1 <= b，c <= m2 <= d
(1)当op[i+s] = ‘+’时，显然有a + c <= m <= b + d
(2)当op[i+s] = ’*’时，有
min {ac，ad，bc，bd} <= m <= max {ac，ad，bc，bd}
换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。
实现：
/* 主题：多边形游戏* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：C++* 开发环境：Vicrosoft Visual Studio* 时间: 2010.11.15*/#include <iostream>#include <vector>using namespace std ;struct SegInfo{public: SegInfo () : m_nMaxValue (0), m_nMinValue(0) {} SegInfo (int maxValue, int minValue) : m_nMaxValue (maxValue), m_nMinValue (minValue) {}public: int m_nMaxValue ; int m_nMinValue ;} ;class PolyGame {public: PolyGame (const vector<char>& op, const vector<int>& vertex) { m_vcOp = op ; m_vnVertex = vertex ; m_nCount = m_vcOp.size () ; m_vSeg.resize (m_nCount) ; for (int i = 0; i < m_nCount; ++ i) { m_vSeg[i].resize (m_nCount) ; } } int beginCalulate () { // 初始边界 for (int i = 1; i < m_nCount; ++ i) { m_vSeg[i][1].m_nMaxValue = m_vnVertex[i] ; m_vSeg[i][1].m_nMinValue = m_vnVertex[i] ; } // i: 起点 // j: 长度 // s: 子切分位置 for (int j = 2; j < m_nCount ; ++ j) { for (int i = 1; i < m_nCount; ++ i) { for (int s = 1; s < j; ++ s) { SegInfo si = __calMinAndMax(i, s, j) ; if (m_vSeg[i][j].m_nMinValue > si.m_nMinValue) { m_vSeg[i][j].m_nMinValue = si.m_nMinValue ; } if (m_vSeg[i][j].m_nMaxValue < si.m_nMaxValue) { m_vSeg[i][j].m_nMaxValue = si.m_nMaxValue ; } } } } // 找到最大值 int temp = m_vSeg[1][m_nCount - 1].m_nMaxValue ; for (int i = 2; i < m_nCount; ++ i) { if (temp < m_vSeg[i][m_nCount - 1].m_nMaxValue) { temp = m_vSeg[i][m_nCount - 1].m_nMaxValue ; } } m_nResult = temp ; return m_nResult ; }private: // 从i开始，长度为j，s为切分位置 SegInfo __calMinAndMax (int i, int s, int j) { int minL = 0 ; int maxL = 0 ; int minR = 0 ; int maxR = 0 ; minL = m_vSeg[i][s].m_nMinValue ; maxL = m_vSeg[i][s].m_nMaxValue ; int r = (i + s - 1) % (m_nCount - 1) + 1 ; minR = m_vSeg[r][j - s].m_nMinValue ; maxR = m_vSeg[r][j - s].m_nMaxValue ; SegInfo si ; // 处理加法 if (m_vcOp[r] == '+') { si.m_nMinValue = minL + minR ; si.m_nMaxValue = maxL + maxR ; } else { // 处理乘法 vector<int> mm ; mm.push_back (minL * minR) ; mm.push_back (minL * maxR) ; mm.push_back (maxL * minR) ; mm.push_back (maxL * maxR) ; int min = 0 ; int max = 0 ; for (vector<int>::iterator ite = mm.begin(); ite != mm.end() ; ++ ite) { if (*ite < min) { min = *ite ; } if (*ite > max) { max = *ite ; } } si.m_nMinValue = min ; si.m_nMaxValue = max ; } return si ; }private : vector<char> m_vcOp ; // 运算符(下标从1开始) vector<int> m_vnVertex ;// 顶点值(下标从1开始) int m_nCount ; // 边的个数 int m_nResult ; // 结果 vector<vector<SegInfo> > m_vSeg ;// 合并后的信息} ;int main(){ const int cnCount = 5 ; vector<char> op (cnCount + 1); vector<int> vertex (cnCount + 1); op[1] = '+' ; op[2] = '*' ; op[3] = '+' ; op[4] = '*' ; op[5] = '*' ; vertex[1] = 10 ; vertex[2] = -8 ; vertex[3] = 3; vertex[4] = -2 ; vertex[5] = -1 ; PolyGame pg (op, vertex) ; cout << pg.beginCalulate () << endl ;}
中查找“C++动态规划”更多相关内容
中查找“C++动态规划”更多相关内容更多精彩
赞助商链接
