最优解的复杂度会不会很高?
原题链接:18537.我心中珍藏的游戏2024-03-18 10:56:54
发布于:浙江
heaviest simple path,会不会是NP?贪心得到的不一定是最优。
提交记录里的算法,对以下构造的权重矩阵会得出错误的答案:
0 1 4 1
1 0 5 1
4 5 0 3
1 1 3 0
可能是把多个技能都和技能3连接了
全部评论 2
也是我的问题,题目一开始没有写清楚。
2024-03-18 来自
1一个可行的解是在使用技能1、2、4之后,连续使用3个加成3+5+4获得12点伤害。
2024-03-18 来自
1
理论上只要图上不出现环即可。不是找最长的路径,而是生成树就行了。可以看一下比赛时补充样例中的例子。
2024-03-18 来自
0其实一开始我想搞路径的,就是有向无环路径问题。但想来想去还是改成了无向图,因为确实是一个NP问题,只能暴力解。
2024-03-18 来自
1
有帮助,赞一个