有n个建筑,每个建筑有两个权值(h[i],w[i]) ,h[i]表礻建筑的高度,w[i]表示拆除建筑的费用.
现在要在除了头尾之外的n-2个建筑内选择若干个保留,并且保留头尾的建筑.
这样的费用为拆除所有没有保留建筑的费用+相邻的保留两个建筑高度差的平方.

首先有一个简单的dp思路
dp[i] 表示保留建筑i的最小费用.
${}_{}^{}$

然后就能获得40分的好成绩

然后来处理一下这個式子.

每次查询就是给出一个x

一个解决方法是CDQ分治

可以发现需要操作的只有插入线和询问点的最大值.

实现比较容易而且跑得快.