令\(S_{i} =\sum_{j=1}^{i}j\) , \(f_{i}\) 为处理到第 \(i\) 个位置放置守卫塔的最小花费。
观察题意，容易得到在\((1<=j<=i-1)\) 时，有
\(f_{i}= min\left \{ f_{j}+\sum_{k=j+1}^{i-1} (i-k)+a_{i} \right \}\) ①
\(f_{i}= min\left \{ f_{j}+\sum_{k=j+1}^{i-1} (i-k) \right \} +a_{i}\) ②
\(f_{i}= min\left \{ f_{j}+\sum_{k=j+1}^{i-1}i-\sum_{k=j+1}^{i-1}k \right \} +a_{i}\) ③
\(f_{i}= min\left \{ f_{j}+(i-j-1)*i-\sum_{k=j+1}^{i-1}k \right \} +a_{i}\) ④
\(f_{i}= min\left \{ f_{j}+(i-j-1)*i-(S_{i-1}-S_{j} ) \right \} +a_{i}\) ⑤
此时若存在 \(k<j\) ，且 \(j\) 比 \(k\)更优时，则\(f_{j}+(i-j-1)*i-(S_{i-1}-S_{j} )<f_{k}+(i-k-1)*i-(S_{i-1}-S_{k} )\) ⑥ ，化简得 $\frac{f_{j}-f_{k}+S_{j}-S_{k}}{j-k}<i $ ⑦。
接着维护一个单调队列，复杂度 \(O(n\times \log_{}{n} )\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll a[1000001],sum[1000001],f[1000001],q[1000001];
double work(ll x,ll y)//注意精度问题
{
return 1.0*(f[y]-f[x]+sum[y]-sum[x])/(y-x);
}
int main()
{
ll n,i,l=0,r=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+i;
}
for(i=1;i<=n;i++)
{
while(l<r&&work(q[l],q[l+1])<i)
{
l++;
}
f[i]=f[q[l]]+(i-q[l]-1)*i-(sum[i-1]-sum[q[l]])+a[i];//直接套公式⑤
while(l<r&&work(q[r-1],q[r])>work(q[r],i))
{
r--;
}
r++;
q[r]=i;
}
cout<<f[n];
return 0;
}
写在最后：十年OI一场空，不开long long见祖宗。