目录
显示
题目链接
https://www.luogu.com.cn/problem/P3628
题解
设 \(s_i\) 为 \(x\) 的前缀和,\(g(x)\) 为那个二次函数,\(f_i\) 为前 \(i\) 个人的最大战斗力。
显然有:
$$f_i=\min_{0 \leq j \lt i} f_j+g(s_i-s_j)$$
时间复杂度 \(O(n^2)\)。
后面那个函数与 \(i,j\) 都有关,考虑斜率优化。
设决策 \(j\) 优于决策 \(k\),从而得到:
$$f_i+g(s_i-s_j) \gt f_i+g(s_i-s_k)$$
整理一下式子后得到(中间过程略):
$$s_i \lt \frac{(f_j+As_j^2-Bs_j)-(f_k+As_k^2-Bs_k)}{2A(s_j-s_k)}$$
用单调队列维护即可,时间复杂度 \(O(n)\)。
#include <iostream> #include <algorithm> using namespace std; int n,a,b,c; long long x[1000005],f[1000005]; int q[1000005],l,r; double slope(int p,int q) { return ((f[p]-b*x[p]+a*x[p]*x[p])-(f[q]-b*x[q]+a*x[q]*x[q]))/(2.0*a*(x[p]-x[q])); } long long calc(long long x) { return a*x*x+b*x+c; } int main() { cin>>n>>a>>b>>c; for(int i=1;i<=n;i++) { cin>>x[i]; x[i]+=x[i-1]; } for(int i=1;i<=n;i++) { while(l<r&&slope(q[l],q[l+1])<=x[i]) l++; int u=q[l]; f[i]=f[u]+calc(x[i]-x[u]); while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--; q[++r]=i; } cout<<f[n]<<endl; return 0; }