目的是dp[i]最小类似线性规划,你有一条直线和一堆点(以前算过的j点),那么就是寻找一个j点使得截距最小 这样就是用单調队列维护一个下凸包(倒U型),只有最外层对应下凸包的点才有意义选这里面的点才能保证斜率最低。 队首两点斜率小于2 * a[i]那就去掉隊首,因为直线肯定不会交到队首剩下的那个点就是与直线相交的点 q[r]和q[r-1]的斜率大于q[i]和q[r]的斜率,意味着这里凹进去了肯定选不到r这个点,出队尾 维护下凸包的意义在于,截距尽可能小的候选点只在这之间