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

2024-09-01 17:58

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

题目:单人游戏,开始有一个由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();
    }
}

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



http://www.chinasem.cn/article/1127653

相关文章

解决pandas无法读取csv文件数据的问题

《解决pandas无法读取csv文件数据的问题》本文讲述作者用Pandas读取CSV文件时因参数设置不当导致数据错位,通过调整delimiter和on_bad_lines参数最终解决问题,并强调正确参... 目录一、前言二、问题复现1. 问题2. 通过 on_bad_lines=‘warn’ 跳过异常数据3

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499

kkFileView启动报错:报错2003端口占用的问题及解决

《kkFileView启动报错:报错2003端口占用的问题及解决》kkFileView启动报错因office组件2003端口未关闭,解决:查杀占用端口的进程,终止Java进程,使用shutdown.s... 目录原因解决总结kkFileViewjavascript启动报错启动office组件失败,请检查of

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

游戏闪退弹窗提示找不到storm.dll文件怎么办? Stormdll文件损坏修复技巧

《游戏闪退弹窗提示找不到storm.dll文件怎么办?Stormdll文件损坏修复技巧》DLL文件丢失或损坏会导致软件无法正常运行,例如我们在电脑上运行软件或游戏时会得到以下提示:storm.dll... 很多玩家在打开游戏时,突然弹出“找不到storm.dll文件”的提示框,随后游戏直接闪退,这通常是由于

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map