[洛谷 3628][APIO2010]特别行动队

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据