多边形游戏

多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

1 将一条边删除。

2 随后n-1步按以下方式操作:

  (1)选择一条边E以及由E连接着的2个顶点V1和V2;

  (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

3 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。

思路:

在所给多边形中,从顶点i(1≤i≤n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j) 可表示为v[i],op[i+1],…,v[i+j-1]。

如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1),则可在op[i+s]处将链分割为2个子链p(i,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}

换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。

核心思想:

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);
}

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];
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

送书 | 跟我一起学《流畅的Python》

本文引自图灵新书《流畅的Python》的第一章——Python数据模型。本书由奋战在Python开发一线近20年的Luciano Ramalho执笔,Victo...

3904
来自专栏zaking's

js算法初窥03(搜索及去重算法)

1282
来自专栏PPV课数据科学社区

零基础到精通Python,从这篇文章开始

关键词:Python,入门 正文: 本文由rever4433, Tocy, Tony, 南宫冰郁, 透过树叶的光等协作翻译,发表于开源中国。 什么是 Pytho...

2946
来自专栏小樱的经验随笔

Vijos P1785 同学排序【模拟】

同学排序 描述 现有m位同学,第1位同学为1号,第2位同学为2号,依次第m位同学为m号。要求双号的学生站出来,然后余下的重新组合,组合完后,再次让双号的学生站出...

2684
来自专栏owent

不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

621
来自专栏进击的程序猿

进击算法:字符串匹配的 BM 算法

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

2532
来自专栏web编程技术分享

JavaScript: 零基础轻松学闭包(2)

2789
来自专栏编程

Python利器之迭代器

各位小伙伴们 大家周四愉快 今天要和大家探讨一个 Python的特色功能 也是Python有别于其他变成语言的 强大利器 迭代器 迭代这一个词可能有的小伙伴不理...

1907
来自专栏前端布道

JavaScript 浮点数陷阱及解法

众所周知,JavaScript 浮点数运算时经常遇到会 0.000000001 和 0.999999999 这样奇怪的结果,如 0.1+0.2=0.300000...

2263
来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

732

扫码关注云+社区

领取腾讯云代金券