这个算法应该怎么实现呢,算法盲有点头疼

2020-11-15 22:21:40 +08:00
 asuka321

背景

朋友在玩一个手游,里面有正邪 2 种性格设定,正邪性格内各分为 6 种命格,正邪内对应命格不能同时存在(如下图正义和邪恶不能同时存在),但可以将一种命格清 0 积累相反的命格点数,命格点数到了之后可以换相应的称谓,要算出拿到以下所有称号需要的最短时间。

逻辑表达

  1. 存在 A,B,C,D,E,F 六种正义属性和 A',B',C',D',E',F'六种邪恶属性,每种属性有一定的属性值;
  2. A 和 A'不能同时存在(其余属性同理),但可以将 A 转换为 A',但转换过会属性值会变为 0;
  3. 每天每种属性都可以加 10 点,也可以不加。相反属性允许同时相加,如给 A 加了 10 点属性值,A'再加 10 点等于给 A 减了 10 点属性值;
  4. 初始状态为邪恶属性值全满,可以理解为邪恶属性初始值无限大;
  5. 需要的称号如上图所示;

当前思路

没有思路,感觉上可以抽象成点到点的最短路径问题,但因为有转换清 0 的存在好像又不是这样=。=

3036 次点击
所在节点    程序员
12 条回复
lihongming
2020-11-16 02:01:57 +08:00
看得不是很明白,几个问题:

1 、称号所需的属性值,是必须为这个数值,还是可以超过?没有值的属性是不考虑,还是必须为 0 ?

2 、相反的属性转换是什么意思?比如 A 本来有 100 点,转换成 A’以后,A’到底有 100 点还是 0 点?如果是 0 点的话,那第二条规则是不是可以描述为——各属性值可以主动清零?

3 、每天每种属性可以加 10 点那条规则,如果 A 本来有 100 点,今天选择给 A’加 10 点,是不是会变成 A 剩 90 点?如果是的话,那第三条规则是不是可以描述为——每天可以选择给每对属性加减 10 点?
binux
2020-11-16 04:18:50 +08:00
一共 12 个顶点,算两两间距离为转换时间,算最短路径
ciddechan
2020-11-16 08:45:20 +08:00
Dijkstra ?
asuka321
2020-11-16 09:53:22 +08:00
@lihongming
1. 可以超过,属性值到了就可以拿到称号,拿到后属性值不变
2. 是的,即属性值能主动清 0
3. 是的,可以选择减 10 点,但如果是为了加相反属性的点数,应该先请 0 再加比较好

我把题目描述做下修改,表述能相对清晰点
asuka321
2020-11-16 09:59:57 +08:00
@binux
@ciddechan
点与点之间的距离怎么计算呢,两个属性值之间可以涉及多个称号,比如图里的超然和桀骜
qinyusen
2020-11-16 10:20:54 +08:00
最小费用最大流
binux
2020-11-16 10:26:19 +08:00
@asuka321 #5 称谓作为顶点而不是命格
lijialong1313
2020-11-16 10:47:26 +08:00
12 维的空间数组?
例如爱憎分明可以表示为:a[][][][][-30][320],守身如玉可表示为:a[][][][-160][][30]
就是求空间最短路
Edward0Chan
2020-11-16 14:13:16 +08:00
@binux #2 不行吧,每个属性每天都可以+10,那就是同时走六条路。你说的是一条路的情况吧
Edward0Chan
2020-11-16 14:21:14 +08:00
称号对应的多个属性值 是 或还是与的关系啊?
也就是只要满足一个属性值就行,还是满足称号下的所有属性才行?
binux
2020-11-16 14:47:26 +08:00
@Edward0Chan 算两点间距离的时候,考虑前序就行了。
asuka321
2020-11-16 15:14:10 +08:00
@Edward0Chan 满足所有属性才行

@binux 不同的前序会导致点与点之间的距离发生变化的,而且距离的值也不好算,距离的值取决于属性的变化规则的。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/725553

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX