题解：P5665 [CSP-S2019] 划分

先考虑暴力，设

dp(i,j)

表示最后一段分割在区间

[i,j)

上，那么最暴力的就是

O(n^3)

枚举，我们发现

dp(j,k) \to dp(i,j)

对于每一个

j

可选的

k

集应该是不断增大的，于是我们可以对于每一个

j

单调队列，复杂度

O(n^2)

。

其实我们可以配合贪心通过一些数学性质来解决这个问题或者打表，就像方差那题一样。对于这题显然越大的数，平方越大，也就是

(a+b)^2 \ge a^2+b^2

，于是我们需要保证最后一段划分尽可能小，也就是这么多段尽可能接近或者说划分更多段。

于是我们设出

f_i

表示前

i

个数的答案，

g_i

表示最后一段划分的和。这样只需要每次找到最大的

j

满足

sum_{j+1,i} \ge g_j

进行转移即可。即

pre_i \ge g_j+pre_j

，相同变量在一侧，单调队列即可。注意

g_i

不一定大于

g_{i-1}

，只是要求大于前一段并不是大于上一个位置。

时间复杂度

O(n)

。

CPP

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=4e7+10;
const int maxm=1e5+10;
const int mod=(1<<30);
long long pre[maxn],g[maxn]; int top=0;
int q[maxn],p[maxm],l[maxm],r[maxm],b[maxn],a[60];
inline long long calc(int x){ return 2*pre[x]-pre[g[x]]; }
inline long long val(int x){ return pre[x]-pre[g[x]]; }
void print(__int128 ans){
	while(ans){
		a[++top]=ans%10;
		ans/=10;
	}
	while(top) cout<<a[top--];
}
int main(){
	int n,type; cin>>n>>type;
	if(!type){
		pre[0]=0;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			pre[i]=pre[i-1]+x;
		}
	}else{
		int x,y,z,m;
		cin>>x>>y>>z>>b[1]>>b[2]>>m;
		for(int i=1;i<=m;i++) cin>>p[i]>>l[i]>>r[i];
		for(int i=3;i<=n;i++) b[i]=(1ll*b[i-1]*x+1ll*b[i-2]*y+z)%mod;
		for(int i=1;i<=m;i++)
			for(int j=p[i-1]+1;j<=p[i];j++){
				x=b[j]%(r[i]-l[i]+1)+l[i];
				pre[j]=pre[j-1]+x;
			}
	}
	q[0]=0; int l=1,r=1; q[1]=0;
	for(int i=1;i<=n;i++){
		while(pre[i]>=calc(q[l+1])&&l<r) l++;
		g[i]=q[l];
		while(calc(i)<=calc(q[r])&&l<=r) r--;
		q[++r]=i;
	}
	int P=n; __int128 ans=0,mul=1;
	while(P){
		mul=val(P); mul=mul*mul;
		ans=ans+mul; 
		P=g[P];
	}
	print(ans);
	return 0;
}

题解：P5665 [CSP-S2019] 划分

文章操作

相关推荐

评论

题解：P5665 [CSP-S2019] 划分