多方形游戏(DP)

Description

多边形游戏是一个单人玩的打,开始时起一个出于n只极点构成的多边形。每个终端被赋予一个平头价值,每条边给授予一个运算符
“+” 或 “*”。所有边依次用整数从1届n编号。

玩耍第1步,将一如既往久边抹。

随后的n-1步按以下办法操作:

(1)选择一样漫漫边E以及由E连年着的个别个顶V1V2

(2)用一个新的巅峰取代边E与由E连接着的简单个终端V1V2。将出于顶点V1V2的整数值通过边E达成的演算得到的结果给新顶点。

末了,所有边还深受删除,游戏结束。游戏之得分就是所留顶点上的整数值。

题材:对于给定的多方形,计算最高得分W ( -231 <
W < 231 )。

戏服务器设计的性质管理器

  游戏中角色有所的属于性值很多,运营多年的嬉戏,往往会来很多只成长线,每个属性都发或给N个成长线模块增减数值。举例当角色戴上铁上hp+100接触,卸下武器时HP-100点,这样加减逻辑只生相同处还于好控制,如果某天有个奇特功能当为某技能攻击时,角色武器会让击落,这样尽管会产出减数值的操作不止一处于。如果逻辑处理不当,比如击落的下从不确切的减数值,再次穿戴武器就招致属性值加了区区边,也尽管是玩家经常说的刷属性。这种bug对戏平衡性影响好要命,反响非常劣质,bug又很麻烦让测试发现。本文将介绍一栽管理性之思路,最要命限度的避免此类bug,如果起bug,也会很好之排查。

Input

输入的首先履是独立一个整数n( 3 ≤ n ≤ 18
),表示多边形的顶点数(同时也是边数)。接下来第n实践,每行包含一个运算符(”+”或”*”)和一个平头V[i](
-10 < V[i] < 10
),分别代表第i条边所对应的运算符和次**i**单极上之数值。

计划思路

  刷属性bug的主干原因是某个功能的模块数值加了N次,所以各个模块加的性要叫记录,加了了必须不能够再加。设计这样的数据结构。

//!各个属性对应一个总值
//!各个属性对应各个模块的分值
template<typename T>
class PropCommonMgr
{
public:
    typedef T ObjType;
    typedef int64_t (*functorGet)(ObjType);
    typedef void (*functorSet)(ObjType, int64_t);
    struct PropGetterSetter
    {
        PropGetterSetter():fGet(NULL), fSet(NULL){}        
        functorGet fGet;
        functorSet fSet;
        std::map<std::string, int64_t> moduleRecord;
    };
    void regGetterSetter(const std::string& strName, functorGet fGet, functorSet fSet){
        PropGetterSetter info;
        info.fGet = fGet;
        info.fSet = fSet;
        propName2GetterSetter[strName] = info;
    }
  public:
      std::map<std::string, PropGetterSetter>    propName2GetterSetter;
  };
  1. 有关数据结构的get和set,我们啊每个属性命名一个名,这样处理数量的时节会格外便于(比如道具配增加属性等等),角色属性有许多种,这里不能够挨个定义,所以属性管理器只是映射属性,并无创造属性值。通过regGetterSetter接口,注册get和set的操作映射。为什么不欲提供add和sub接口能,因为add和sub可以经过get和set组合实现。get和set的接口实现如下:

    int64_t get(ObjType obj, const std::string& strName) {

        typename std::map<std::string, PropGetterSetter>::iterator it = propName2GetterSetter.find(strName);
        if (it != propName2GetterSetter.end() && it->second.fGet){
            return it->second.fGet(obj);
        }
        return 0;
    }
    bool set(ObjType obj, const std::string& strName, int64_t v) {
        typename std::map<std::string, PropGetterSetter>::iterator it = propName2GetterSetter.find(strName);
        if (it != propName2GetterSetter.end() && it->second.fSet){
            it->second.fSet(obj, v);
            return true;
        }
        return false;
    }
    
  2. 关于add和sub,前面提到要避免刷属性,就必避免重复加属性。所以每个模块再加属性前务必检查一下是否该模块已加了性能,如果加了得要是先期减后加。因为老是模块加属性都记录在性能管理器中,那么减掉的数值肯定是无可非议的。这样可以避另外一栽常见bug,如加了100,减的时段计算错误减了80,也会见积少成多招刷属性。add和sub的代码如下:

    int64_t addByModule(ObjType obj, const std::string& strName, const std::string& moduleName, int64_t v) {

        typename std::map<std::string, PropGetterSetter>::iterator it = propName2GetterSetter.find(strName);
        if (it != propName2GetterSetter.end() && it->second.fGet && it->second.fSet){
            int64_t ret =it->second.fGet(obj);
            std::map<std::string, int64_t>::iterator itMod = it->second.moduleRecord.find(moduleName);
            if (itMod != it->second.moduleRecord.end()){
                ret -= itMod->second;
                itMod->second = v;
            }
            else{
                it->second.moduleRecord[moduleName] = v;
            }
            ret += v;
            it->second.fSet(obj, ret);
            return ret;
        }
        return 0;
    }
    int64_t subByModule(ObjType obj, const std::string& strName, const std::string& moduleName) {
        typename std::map<std::string, PropGetterSetter>::iterator it = propName2GetterSetter.find(strName);
        if (it != propName2GetterSetter.end() && it->second.fGet && it->second.fSet){
            int64_t ret =it->second.fGet(obj);
            std::map<std::string, int64_t>::iterator itMod = it->second.moduleRecord.find(moduleName);
            if (itMod == it->second.moduleRecord.end()){
                return ret;
            }
            ret -= itMod->second;
            it->second.moduleRecord.erase(itMod);
            it->second.fSet(obj, ret);
            return ret;
        }
        return 0;
    }
    int64_t getByModule(ObjType obj, const std::string& strName, const std::string& moduleName) {
        typename std::map<std::string, PropGetterSetter>::iterator it = propName2GetterSetter.find(strName);
        if (it != propName2GetterSetter.end() && it->second.fGet && it->second.fSet){
            int64_t ret =it->second.fGet(obj);
            std::map<std::string, int64_t>::iterator itMod = it->second.moduleRecord.find(moduleName);
            if (itMod != it->second.moduleRecord.end()){
                return itMod->second;
            }
        }
        return 0;
    }
    std::map<std::string, int64_t> getAllModule(ObjType obj, const std::string& strName) {
        std::map<std::string, int64_t> ret;
        typename std::map<std::string, PropGetterSetter>::iterator it = propName2GetterSetter.find(strName);
        if (it != propName2GetterSetter.end() && it->second.fGet && it->second.fSet){
            ret = it->second.moduleRecord;
        }
        return ret;
    }
    

  如齐代码所示,addByModule和subByModule必须提供模块名,比如通过装备的时加血量:addByModule(‘HP’,
‘Weapon’, 100),而下武器的时节要subByModule(‘HP’,
‘Weapon’),因为性管理器知道减多少。

Output

输出只来一个整数,表示最高得分W

总结

  1. 性提供一个名映射出无数补,比如装备配属性,buff配属性的,有名字不无关系联会特别福利
  2. 供一个get和set接口的照耀,这样属性管理器就与具体的靶子的性质字段解耦了。即使是并存的功能模块也得合这个特性管理器。
  3. 特性的add和sub操作,都于性能管理器中留下记录,这样尽管出现问题,通过getByModule
    getAllModule两独接口也足帮助查找问题。
  4. 性能管理就合龙到H2Engine中,github地址:
    https://github.com/fanchy/h2engine

Sample Input

**3

  • 2
    * 3
  • 1**

Sample Output

9

#include<string.h>
#include<stdio.h>
#include<iostream>
#define MAX 102
using namespace std;
int v[MAX];
char op[MAX];
int n,minf,maxf;
int m[MAX][MAX][2];
void minMax(int i,int s,int j)
{
    int e[5];
    int a=m[i][s][0],
        b=m[i][s][1],
        r=(i+s-1)%n+1,
        c=m[r][j-s][0],
        d=m[r][j-s][1];
    if(op[r]=='+')
    {
        minf=a+c;
        maxf=b+d;
    }
    else
    {
        e[1]=a*c;
        e[2]=a*d;
        e[3]=b*c;
        e[4]=b*d;
        minf=e[1];
        maxf=e[1];
        for(int k=2; k<5; k++)
        {
            if(minf>e[k])
                minf=e[k];
            if(maxf<e[k])
                maxf=e[k];
        }
    }
}
int polyMax(){
    for(int i=1;i<=n;i++)
        for(int j=2;j<=n;j++){
            m[i][j][0]=1000000;
            m[i][j][1]=-1000000;
        }
    for(int j=2; j<=n; j++)
        for(int i=1; i<=n; i++)
            for(int s=1; s<j; s++)
            {
                minMax(i,s,j);
                if(m[i][j][0]>minf)
                    m[i][j][0]=minf;
                if(m[i][j][1]<maxf)
                    m[i][j][1]=maxf;
            }
    int temp=m[1][n][1];
    for(int i=2; i<=n;i++)
        if(temp<m[i][n][1]) temp=m[i][n][1];
    return temp;
}
int main()
{
    memset(m,0,sizeof(m));
    cin >> n;
    getchar();
    for(int i=1;i<=n;i++)
    {
        cin >> op[i] >> v[i];
        getchar();
        m[i][1][0]=m[i][1][1]=v[i];
    }
    cout << polyMax() <<endl;
    return 0;
}