题解

1 条题解

  • 0
    @ 2021-08-19 11:37:17

    显然区间dp,因为是个环,在后面也复制一遍,
    设dp[i][j] 表示区间[i,j]内的人比完以后总共的能力值差的绝对值之和的最小值。

    然后处理出所有区间的最大值,因为一个区间最后比剩下的一定是能力值最大的,用记录MAX[i][j] 的 最 大 能 力 值 [i,j]的最大能力值[i,j]的最大能力值)

    然后转移dp[i][j] = min { dp[i][k]+dp[k+1][j]+ | MAX[i][k]-MAX[k+1][j]| | i<=k<j }

  • 1

信息

ID
1180
难度
9
分类
动态规划 点击显示
标签
递交数
2
已通过
1
通过率
50%
被复制
6
上传者