1 条题解
-
0
何老师 (root) LV 0 MOD @ 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