由于第一个小时在面试,最后总的算下来只有半个小时在笔试,最后一题后面想了一个平方级别的算法,评论区貌似只有立方级别的做法。 首先枚举i,j表示最后两个是那两个位置,暂且叫做dpij。 然后我们考虑极端情况,全部是0,那么ij可以转移到任何一个位置,复杂度=状态数*状态转移=n^3 肯定是不行的。 那么怎么办,我们贪心一下,ij只转移到里ak=ai+aj,ak是离ij最近的位置,可以把后面的ak都不用考虑 这一步贪心可以省去一个n的复杂度。 然后就很简单了,由于上面的贪心,dpij只可能转移到唯一一个dp[i'][j'] 状态转移只要O(1),状态数要n...