有N个序列,在每轮要么有一个数值,要么轮空。将序列进行排序,每轮选取没有轮空的排在最前的序列的数值。
问序列按什么顺序排序时,各轮的数值之和最大?
示例:
轮 1 | 轮 2 | 轮 3 | |
---|---|---|---|
序列 A | 5 | 2 | 3 |
序列 B | 1 | ||
序列 C | -9 | 9 | |
序列 D | -20 | 15 |
各排序结果的值:
排序 | 轮1 | 轮2 | 轮3 | 和 |
---|---|---|---|---|
ABCD | 5 | 2 | 3 | 10 |
ABDC | 5 | 2 | 3 | 10 |
ACBD | 5 | 2 | 3 | 10 |
ACDB | 5 | 2 | 3 | 10 |
ADBC | 5 | 2 | 3 | 10 |
ADCB | 5 | 2 | 3 | 10 |
BACD | 5 | 1 | 3 | 9 |
BADC | 5 | 1 | 3 | 9 |
BCAD | 5 | 1 | 9 | 15 |
BCDA | -20 | 1 | 9 | -10 |
BDAC | -20 | 1 | 15 | -4 |
BDCA | -20 | 1 | 15 | -4 |
CABD | 5 | -9 | 9 | 5 |
CADB | 5 | -9 | 9 | 5 |
CBAD | 5 | -9 | 9 | 5 |
CBDA | -20 | -9 | 9 | -20 |
CDAB | -20 | -9 | 9 | -20 |
CDBA | -20 | -9 | 9 | -20 |
DABC | -20 | 2 | 15 | -3 |
DACB | -20 | 2 | 15 | -3 |
DBAC | -20 | 1 | 15 | -4 |
DBCA | -20 | 1 | 15 | -4 |
DCAB | -20 | -9 | 15 | -14 |
DCBA | -20 | -9 | 15 | -14 |
最终BCAD排列的和最大,为所求结果。
(上述为举例,序列数和轮数不定。求一个能算出结果的算法或数据结构,不要穷举)
参考下下面链接
https://zh.cppreference.com/w/c/language/operator_logical
这个应该可以这么考虑
把每个序列分为轮空的项和非空的项, 总共n项, 序列总共m行,记录为Xm
假设Xm每个序列 轮空的项集合 Ak=a1 a2 a3 ... ak 非空的项集合是 Bp = b1 b2 ... bp,
k+p = n
那么对于每个Xm能够取到的最大值是:集合Bp之和 + 其它项对应Ai位置最大的值(max(Ak))之和
参考上面的例子:
序列B, 轮空集合 Ak = a1 a3, 非空集合是 Bp = b2
那么序列B这轮最大的值就是 b2 + max(a1第一轮其它序列的值) + max(a3第三轮其它序列的值) = 1 + 5 + 9 = 15
这个代码实现起来是比较简单的
esay