遇到一个求权值最小和问题，求解答。
Tom 有一天在玩棋子，这些棋子都不是普通的棋子。现在有 n 个棋子排成一排(2<=n<=18)，每个棋子都有它们自己的权值 ai(0<=ai<=1e9)，现在 Tom 每次选择连续的三枚棋子，然后中间的那枚棋子会消失，而它左右两边的棋子会分别加上它的权值，问最后只剩下两枚棋子的时候，这两枚棋子的权值的最小的和为多少？输入棋子个数 n 和一个数组 a，a[i] 表示每个棋子的权值。输出一个数，表示最终剩下的两枚棋子的权值的最小的和。
展开
收起
1
条回答
写回答
写回答
-
因为我们每选择一次，消失的数对左右都有影响，而且也会被挑选的顺序影响，所以需要去考虑每个棋子的贡献。枚举一段区间最后选的棋子，然后将其分为两段区间，设该段区间的左端点最终的贡献为 x，右端点最终的贡献为 y，那么在只剩最后选的数，左端点，右端点三个点时，我们选择最后的那个点，那么最后那个数最终的贡献就是 x+y 次了，然后根据这个思路已知分治下取就好了。dfs(l,r,x,y) 表示左端点、右端点、左端点的贡献、右端点的贡献的区间合并成两个数的最小和。 因此输入：4 [1,2,3,4] 输出：17
2021-12-23 18:49:52赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
