笔记-[APIO2010]特别行动队

[APIO2010]特别行动队

\(f_i\) 表示将 \((j+1,j+2,\dots,i)\) 分为一组，已解决 \(i\) 之前的士兵的最小代价。

\(a<0\)。

\[\begin{split}
f_i=&\max\{f_j+aX^2+bX+c\}(j<i)\\
=&\max\{f_j+a\left(\sum_{h=j+1}^ix_h\right)^2+b\left(\sum_{h=j+1}^ix_h\right)+c\}\\
\end{split}
\]

设 \(s_i=\sum_{h=1}^i x_h\)：

\[\begin{split}
f_i=&\max\{f_j+a\left(\sum_{h=j+1}^ix_h\right)^2+b\left(\sum_{h=j+1}^ix_h\right)+c\}\\
=&\max\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}\\
=&\max\{f_j+a(s_i^2-2s_is_j+s_j^2)+b(s_i-s_j)+c\}\\
=&\max\{f_j+as_i^2-2as_is_j+as_j^2+bs_i-bs_j+c\}\\
=&\max\{f_j-2as_is_j+as_j^2-bs_j\}+as_i^2+bs_i+c\\
\end{split}
\]

考虑 \(j=k\) 比 \(j=t\) 更优：

\[\begin{split}
f_k-2as_is_k+as_k^2-bs_k>&f_t-2as_is_t+as_t^2-bs_t\\
f_k-2as_is_k+as_k^2-bs_k>&f_t-2as_is_t+as_t^2-bs_t\\
(f_k+as_k^2-bs_k)-(f_t+as_t^2-bs_t)>&2as_is_k-2as_is_t\\
\frac{(f_k+as_k^2-bs_k)-(f_t+as_t^2-bs_t)}{s_k-s_t}>&2as_i\\
\end{split}
\]

搞定。

Code

#include <bits/stdc++.h>

using namespace std;

//Start

#define re register

#define il inline

#define mk make_pair

#define pb push_back

#define db double

#define lng long long

#define fi first

#define se second

const int inf=0x3f3f3f3f;

const lng INF=0x3f3f3f3f3f3f3f3f;

//Data

int n,a,b,c;

vector<int> x;

vector<lng> s,f;

//DP

template<typename T> il T p2(re T x){return x*x;}

il db fx(re int x){return s[x];}

il db fy(re int x){return f[x]+p2(s[x])*a-s[x]*b;}

il db slope(re int k,re int t){return (fy(k)-fy(t))/(fx(k)-fx(t));}

il lng DP(){

	re int l=1,r=0; re vector<int> q(n+7); q[++r]=0;

	for(re int i=1;i<=n;i++){

		while(l<r&&slope(q[l],q[l+1])>=s[i]*2*a) l++;

		f[i]=f[q[l]]+p2(s[i]-s[q[l]])*a+(s[i]-s[q[l]])*b+c;

		while(l<r&&slope(q[r-1],q[r])<=slope(q[r],i)) r--;

		q[++r]=i;

	}

	return f[n];

}

//Main

int main(){

	scanf("%d%d%d%d",&n,&a,&b,&c);

	x=vector<int>(n+7);

	s=f=vector<lng>(n+7);

	for(re int i=1;i<=n;i++)

		scanf("%d",&x[i]),s[i]=s[i-1]+x[i];

	printf("%lld\n",DP());

	return 0;

}

\[\Huge\color{#ddd}{\texttt{---END---}}
\]

巴特西

笔记-[APIO2010]特别行动队

笔记-[APIO2010]特别行动队

Code

最新文章

热门文章