正题

题目链接: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>
using namespace std;
const int N=2100;
struct node{
	int l,r;
}q[110000];
int n,m,k,t,ans,p[N],st[N][26],ss[N][26],nxt[N],f[N][N],pre[N][N];
char T[N],S[N];
bool cmp(node x,node y)
{return x.l<y.l;}
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	scanf("%s",T+1);m=strlen(T+1);
	scanf("%s",S+1);n=strlen(S+1);
	for(int i=1;i<=m;i++){
		for(int j=0;j<26;j++)
			st[i][j]=st[i-1][j]+(T[i]=='a'+j);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<26;j++)
			ss[i][j]=ss[i-1][j]+(S[i]=='a'+j);
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].l++,q[i].r++;
	sort(q+1,q+1+k,cmp);
	int nowr=0,pr=0;
	for(int i=1;i<=k;i++){
		if(q[i].l>nowr){
			nxt[pr]=nowr;
			for(int j=nowr+1;j<q[i].l;j++)nxt[j]=j;
			pr=q[i].l;nowr=q[i].r;
		}
		else nowr=max(q[i].r,nowr);
	}
	nxt[pr]=nowr;
	for(int i=nowr+1;i<=n;i++)nxt[i]=i;
	for(int i=1;i<=n;i++)
		if(nxt[i])p[++t]=i;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++){
			int l=p[j],r=nxt[l],L=i;
			for(int z=min(r-l,m-L);z>=0;z--){
				bool flag=1;
				for(int k=0;k<26;k++)
					if(ss[r][k]-ss[l-1][k]<st[L+z][k]-st[L-1][k])
						{flag=0;break;}
				if(flag){pre[i][j]=z+1;break;}
			}
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++){
			int l=p[j],r=nxt[l],R=i;
			if(pre[i][j]==r-l+1)continue;
			for(int z=min(r-l,R-1)-1;z>=0;z--){
				bool flag=1;
				for(int k=0;k<26;k++)
					if(ss[r][k]-ss[l-1][k]<st[R][k]-st[R-z-1][k])
						{flag=0;break;}
				if(flag){f[i+1][j+1]=z+1;ans=max(ans,z+1);break;}
			}
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++){
			int l=p[j],r=nxt[l];
			if(pre[i][j]==r-l+1){
				f[i+r-l+1][j+1]=f[i][j]+r-l+1;
				ans=max(ans,f[i][j]+r-l+1);
			}
			ans=max(ans,f[i][j]+pre[i][j]);
		}
	printf("%d\n",ans);
	return 0;
}