考古学家在遗迹中发现了一排共 n 块符文石,每块石头拥有一个整数能量值。他们可以随意重新排列这些石头的顺序(进行任意次两两交换,也可以不交换),随后将执行一种名为“共鸣”的操作。
一次共鸣操作定义为:选取相邻的两块石头,让它们产生共鸣。共鸣后,能量较低的那块石头会粉碎消失,能量较高的那块石头保留在原位,且能量值不变。这次操作的代价等于被保留石头(即两者中能量较高者)的能量值。共鸣后,石头的总数量减少 1。
整个仪式需要恰好执行 n−1 次共鸣操作,直到现场仅剩一块石头。
请设计一种交换策略以及随后的共鸣顺序,使得所有共鸣操作的总代价最小。你需要求出这个最小的总代价。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.