正题

题目链接:https://www.luogu.com.cn/problem/P4983

题目大意

给出长度为\(n\)的序列\(x\)，记平均数为\(\bar{x}\)，要求将序列分成\(m\)段。

每一段\([l,r]\)的值为

\[\frac{((\sum_{i=l}^rx_i\times \bar x)+\bar x)^2}{\bar x^2}
\]

求所有段的值和最小

\(1\leq m\leq n\leq 10^5,1\leq x_i\leq 1000\)

解题思路

直接除以\(\bar x^2\)就是最小化\((\sum_{i=l}^rx_i+1)^2\)的和。

然后这个问题是下凸函数，设\(f(i)\)表示恰好分成\(i\)段，那么显然段数越多答案越小而且每次减少的越少。

所以我们可以用\(wqs\)二分给每次分一个段加上一个权值\(val\)。

那么现在的转移就是

\[F_i=min\{F_j+(s_i-s_j+1)^2+val\}(j<i)
\]

这是经典的斜率优化不过多赘述。

时间复杂度\(O(n\log W)\)（\(W\)表示二分值域）

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1e5+10;

ll n,m,s[N],f[N],g[N],x[N],y[N],q[N];

ll count(ll l,ll r)

{return f[l]+(s[r]-s[l]+1)*(s[r]-s[l]+1);}

ll xj(ll p,ll q,ll z)

{return (x[p]-x[z])*(y[q]-y[z])-(x[q]-x[z])*(y[p]-y[z]);}

ll check(ll val){

	int head=1,tail=0;q[++tail]=0;

	for(ll i=1;i<=n;i++){

		while(head<tail&&2ll*s[i]*(x[q[head+1]]-x[q[head]])>(y[q[head+1]]-y[q[head]]))head++;

		f[i]=count(q[head],i)+val;g[i]=g[q[head]]+1;

		y[i]=f[i]+s[i]*s[i]-2*s[i];x[i]=s[i];

		while(head<tail&&xj(i,q[tail],q[tail-1])>=0)tail--;

		q[++tail]=i;

	}

	return g[n];

}

signed main()

{

	scanf("%lld%lld",&n,&m);

	for(ll i=1;i<=n;i++)

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

	ll l=0,r=1e18;

	while(l<=r){

		ll mid=(l+r)>>1;

		if(check(mid)<=m)r=mid-1;

		else l=mid+1;

	}

	check(l);

	printf("%lld\n",f[n]-l*m);

	return 0;

}

巴特西

P4983-忘情【wqs二分,斜率优化】

正题

题目大意

解题思路

code

最新文章

热门文章