注意:本文比较粗糙,待去锯齿、待优化模型、待优化上色。

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

翻译过标题来就是为什么一个环形的n石子归并可以转化为n个链形的n石子归并

 

两种合并相同的特征有:

1.有n个石子(废话)

2.最后一步合并时总是   没   得   选

 

我能看出来的相同特征只有这   两个     一个,欢迎来访的客人在评论区补充。

 

正文:

在一次石子归并中,最后一次的合并一定发生在某两个区间中,这两个区间的长度和是初始时石子堆的个数。

由于这两个区间具有分明的界限,所以在此之前(此:最后一次合并),这两个区间的界限(一条空想的线)两旁的两个石子堆,只会有一种合并选择(当然不会只有一种选择),

这种合并行为性质和链合并中的链头和链尾的性质相同。

 

所以对于环形石子归并,可以将ta的过程以“最后合并的两个堆的界限”归类,分为n类,

每一类都可以用链状石子归并求解,所以,emmm……。

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄