洛谷 P5665 [CSP-S2019] 划分

链接：

P5665

题意：

给出 \(n\) 个整数 \(a_i\) ，你需要找到一些分界点 \(1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n\)，使得

\(\sum\limits_{i=1}^{k_1} a_i \leq \sum\limits_{i=k_1+1}^{k_2} a_i \leq \cdots \leq \sum\limits_{i=k_p+1}^{n} a_i\)。

注意 \(p\) 可以为 \(0\) 且此时 \(k_0 = 0\)。

请你最小化

\((\sum\limits_{i=1}^{k_1} a_i)^2 + (\sum\limits_{i=k_1+1}^{k_2} a_i)^2 + \cdots + (\sum\limits_{i=k_p+1}^{n} a_i)^2\)。

分析：

根据完全平方公式有：\((a+b)^2\geq a^2+b^2\)

所以分段比不分段更优。其次，对于一个数 \(x\)，将他分到左边和右边会造成 \(2x*sum_{side}+x^2\) 的贡献（\(sum\) 指两区间和），又因为 \(sum_L\leq sum_R\) 所以尽量分到左边更优。也就是说，最后一段和最小时，答案最优。（这个策略还是能猜出来，只是不敢确定）。于是就有后面的\(O(n^2)\) dp 了。

算法：

首先维护一个前缀和 \(sum\) （和上文 \(sum\) 不同）。设 \(d[i]\) 为 \(i\) 结尾，最后一段最小时上一段的结尾位置，于是有 \(d[i]=max\{j|sum[i]-sum[j]\geq sum[j]-sum[d[j]]\}\)。从 \(i\) 向左循环遇到的第一个满足条件的位置就是 \(d[i]\)。输出时从 \(n\) 不停向它的 \(d\) 值跳，一直跳到 \(0\)。复杂度 \(O(n^2)\)。

优化：

根据上述算法可以写出这样的程序：

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

		for(int j=i-1;j>=1;j--)

			if(sum[i]-sum[j]<sum[j]-sum[d[j]]) continue;

			d[i]=j; break;

	}

	int now=n;

	while(now){

		int t=sum[now]-sum[d[now]];

		ans+=t*t;

		now=d[now];

	}

\(O(n^2)\) 复杂度可以通过64分的好成绩，但是看到 \(2\leq n\leq4\times10^7\)，这说明我们需要一个 \(O( n )\) 或实（hen）现（neng）良（ka）好（chang）的 \(O(n\log n)\)。

回顾算法，发现判断 \(j\) 是否合法时的柿子：

\(sum[i]-sum[j]\geq sum[j]-sum[d[j]]\)

可以继续改写：

\(2*sum[j]-sum[d[j]]\leq sum[i]\)

此时左边只与 \(j\) 有关右边只与 \(i\) 有关。设 \(A(j)=2*sum[j]-sum[d[j]]\) 。显然 \(A(j)\) 越小，\(j\) 越可能成为合法答案，所以当存在 \(j_1<j_2\) 且 \(A(j_1)>A(j_2)\) 时，\(j_2\) 比 \(j_1\) 更优。

又有 \(sum[i]\lt sum[i+1]\) 所以当一个 \(j\) 满足 \(A(j)\leq sum[i]\) 时，它也满足 \(A(j)\leq sum[i+1]\)。

基于以上两点我们可以维护出一个 \(A(j)\) 单调上升且 \(j\) 单调上升的单调队列，每次转移时找到最大的满足 \(A(j)\leq sum[i]\) 的 \(j\)，小于 \(j\) 的状态可以舍弃，更新 \(d[i]\) 后将 \(A(i)\) 加入队列尾并弹出 \(A(k)>A(i)\) 的状态 \(k\)，每个点最多进出1次，所以复杂度是 \(O(n)\)。

于是我们可以这样维护 \(d[i]\)：

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

		while(head<tail&&A(q[head+1])<=sum[i])head++;

		d[i]=q[head];

		while(head<tail&&A(i)<A(q[tail]))tail--;

		q[++tail]=i;

	}

另外的，此题最后三个测试点相当毒瘤，输入相当占时间和空间，数据范围会爆 long long。我们不得不选择高精(或考场上不敢写的__int128)，同时需要对空间和时间能够精确把控，最好还是自己慢慢调，可以锻炼自己的代码能力。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define in read()

inline int read(){

	int p=0,f=1;

	char c=getchar();

	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

	return p*f;

}

const int N=4e7+5;

ll sum[N];

int d[N],q[N],n,type,head,tail;

inline __int128 A(int i){return 2*sum[i]-sum[d[i]];}

//sub23~25

const int M=1e5+5;

const int mod=1ll<<30;

ll x,y,z,m;

int p[M],l[M],r[M];

ll b[N];

//

__int128 ans;

void print(__int128 x){

	if(x==0){

		cout<<0;

		return ;

	}

	string res="";

	while(x){

		res+=x%10+'0';

		x/=10;

	}

	reverse(res.begin(),res.end());

	cout<<res;

}

signed main(){

	n=in,type=in;

	if(type==0)

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

			sum[i]=sum[i-1]+in;

	else{

		x=in,y=in,z=in,b[1]=in,b[2]=in,m=in;

		for(int i=1;i<=m;i++)

			p[i]=in,l[i]=in,r[i]=in;

		for(int i=3;i<=n;i++)

			b[i]=((x*b[i-1]%mod+y*b[i-2]%mod)%mod+z)%mod;

		int now=0;

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

			if(i>p[now])now++;

			sum[i]=sum[i-1]+b[i]%(r[now]-l[now]+1)+l[now];

		}

	}

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

		while(head<tail&&A(q[head+1])<=sum[i])head++;

		d[i]=q[head];

		while(head<tail&&A(i)<A(q[tail]))tail--;

		q[++tail]=i;

	}

	int now=n;

	while(now){

		__int128 t=sum[now]-sum[d[now]];

		ans+=t*t;

		now=d[now];

	}

	print(ans);

	return 0;

}

可能是因其毒瘤的数据才成为了紫题

巴特西

洛谷 P5665 [CSP-S2019] 划分

链接：

题意：

分析：

算法：

优化：

代码：

最新文章

热门文章