多边形游戏问题——动态规划

本文主要是介绍多边形游戏问题——动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：单人游戏，开始有一个由n个顶点构成的多边形，每个顶点赋予一个整数值，每条边一个运算符“+”，“ *”

所有边依次用整数1到n编号，

游戏第一步，将一条边删除，随后n-1操作：

选择一条边E及E连接两个顶点V1，V2；用一个新的顶点取代边E及由E连接的两个顶点V1，V2，将由顶点V1和V2整数值通过边E上

的运算得到的结果赋予新顶点，然后所有边呗删除，游戏结束，游戏得分即为所剩顶点整数值

问题：计算最高得分

//多边形游戏

#include<iostream>
using namespace std;
#define N 100
int m[100][100][100];
char op[100];//运算符
int v[100];//顶点数值
int minf,maxf;  
void MinMax(int i, int j, int k)
{
    int e[4], l, 
        a = m[i][k][0], 
        b = m[i][k][1],
        r = (i + k + 1) % N,
        c = m[r][j - k - 1][0],
        d = m[r][j - k - 1][1];


    if (op[(r - 1 + N) % N] == '+') {
        minf = a + c;
        maxf = b + d;
    } else {
        e[0] = a * c;
        e[1] = a * d;
        e[2] = b * c;
        e[3] = b * d;
        minf = e[0];
        maxf = e[0];
        for (l = 1; l < 4; l ++) {
            if (minf > e[l]) minf = e[l];
            if (maxf < e[l]) maxf = e[l];
        }
    }
}
void PolyMax()
{
    int i, j, k, max;


    for (j = 1; j < N; j ++)
        for (i = 0; i < N; i ++)
            for (k = 0; k < j; k ++) {
                MinMax(i, j, k);
                if (m[i][j][0] > minf) m[i][j][0] = minf;
                if (m[i][j][1] < maxf) m[i][j][1] = maxf;
            }


    max = m[0][N - 1][1];
    for (i = 1; i < N; i ++)
        if (max < m[i][N - 1][1]) max = m[i][N - 1][1];


    printf("%d\n", max);
}




int main()
{


    int n;//顶点个数  
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>v[i]>>op[i];
        }
        PolyMax();
    }
}

这篇关于多边形游戏问题——动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---