题目大意：给定一个长为$n$的序列，每个点需要放置一个守卫塔或一个木偶，在第$i$个点放置守卫塔的代价为$a_i$，放置木偶的代价为$j-i$，$j$为$i$右边第一个守卫塔，求最小代价。

题解：$O(n^2)$的$DP$显然，$ f_i=\min\limits_{j < i}\{f_j+a_i+1+2+\dots + (i - j - 2) + (i - j - 1)\}$

$$\begin{align*}

f_i&=\min\limits_{j < i}\{f_j+\frac{(i - j)(i - j - 1)}{2} + a_i\}\\

&=\min\limits_{j < i}\{f_j+\frac{i^2-ij-i+ij+j^2+j}{2}+a_i\}

\end{align*}$$

$$把关于i的部分提出来$$

$$f_i=\min\limits_{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=\min\limits_{j < i}\{y_j+ij\} + a_i+\frac{i^2-i}{2}$$

$$考虑a和b两个决策，若a<b且b比a优$$

$$\therefore y_b-ib<y_a-ia$$

$$\Rightarrow \frac{y_b-y_a}{b-a}<i$$

然后乱搞就好了

卡点：无

 

C++ Code：

#include 
     
      #define int long long#define maxn 1000010using 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\n", f[n]);	return 0;}