题目大意：给定一个长为$n$的序列，每个点需要放置一个守卫塔或一个木偶，在第$i$个点放置守卫塔的代价为$a_i$，放置木偶的代价为$j-i$，$j$为$i$右边第一个守卫塔，求最小代价。
题解：$O(n^2)$的$DP$显然，$ f_i=minlimits_{j < i}{f_j+a_i+1+2+dots + (i - j - 2) + (i - j - 1)}$
$$egin{align*}
f_i&=minlimits_{j < i}{f_j+frac{(i - j)(i - j - 1)}{2} + a_i}\
&=minlimits_{j < i}{f_j+frac{i^2-ij-i+ij+j^2+j}{2}+a_i}
end{align*}$$
$$把关于i的部分提出来$$
$$f_i=minlimits_{j < i}{f_j+frac{j^2+j}{2}+ij} + a_i+frac{i^2-i}{2}$$
$$令y_i=f_i+frac{i^2+i}{2}$$
$$f_i=minlimits_{j < i}{y_j+ij} + a_i+frac{i^2-i}{2}$$
$$考虑a和b两个决策，若a<b且b比a优$$
$$ herefore y_b-ib<y_a-ia$$
$$Rightarrow frac{y_b-y_a}{b-a}<i$$
然后乱搞就好了
卡点：无
C++ Code：
#include <cstdio>
#define int long long
#define maxn 1000010
using namespace std;
int n, a[maxn], f[maxn];
int q[maxn], h, t;
int y(int x) {return f[x] + (x * (x + 1) >> 1);}
double slope(int a, int b) {
return 1.0 * (y(b) - y(a)) / (b - a);
}
signed main() {
scanf("%lld", &n);
h = t = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
while (h < t && slope(q[h], q[h + 1]) <= i) h++;
int tmp = q[h];
f[i] = y(tmp) - i * tmp + a[i] + (i * (i - 1) >> 1);
while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i)) t--;
q[++t] = i;
}
printf("%lld
", f[n]);
return 0;
}