cookiebus 2024-04-24 14:51:48 2024-04-27 10:49:57 14 返回题目
区间DP。最大的放在尽可能远的地方会更优，每个小孩可以选择放区间的最左边或者放区间的最右边。
考虑贪心,显然对于权值大的数,选择最左边和最右边贡献大的位置. 但是如果最左边和最右边贡献一样大,就不好判断了, 因为会影响接下来其他数的贡献, 所以这题应该用dp做,
先对个元素从大到小排序,因为要优先放大的, 令表示i个元素放在最左边,j个元素放在最右边的最大权值和. 枚举每个状态,向下一个状态转移即可.
