题目大意

给定一个序列\(a_1,a_2,...,a_n\)定义它的一个子序列\(a_{i_j},a_{i_2},...,a_{i_k}(i_1<i_2<...<i_k)\)的美丽值为

\[\sum\limits_{j=1}^k-1{\left\lfloor\dfrac{a_{i_{j+1}}}{a_{i_j}}\right\rfloor} \]

求子序列中美丽值最大的

「NOIP2021模拟赛8.18 B」序列（seq）

问题解决

我们很容易写出一个\(DP\)转移方程是\(dp[i]=max(dp[j]+\left\lfloor\dfrac{a_{i}}{a_j}\right\rfloor)\)

然后发现\(\left\lfloor\dfrac{a_{i}}{a_j}\right\rfloor\)的取值实际只有\(\sqrt{a_i}\)个，也就是要想办法取出\(\left\lfloor\dfrac{a_{i}}{a_j}\right\rfloor\)值相同的\(a_j\)的最大值

如何求解\(\left\lfloor\dfrac{a_{i}}{a_j}\right\rfloor\)值相同的\(a_j\)使用数论分块就可以了，复杂度是\(n\sqrt{n}\)的

然后思考查询和修改，这里要思考一个问题，由于\(\left\lfloor\dfrac{a_{i}}{a_j}\right\rfloor\)的值随着\(a_j\)的增大时逐渐减小的，所以\(max(L,R)+val_{i+1}≤max(1,R)+val_{i+1}<max(1,R)+val_i\)由于都是更新\(dp[i]\)所以直接寻找\(max(1,R)\)来代替\(max(L,R)\)更新答案即可

显然，可以用树状数组来维护，但是这样让时间复杂度到达\(n\sqrt{n}logn\)

每次\(\sqrt{n}\)来修改，自然而然想到分块，先建立一个\(a[i]\)到\(dp[i]\)的映射，将分成\(\sqrt{n}\)块，记录下前\(i\)块的最大值\(S[i]\)和每个数在块中的前面的最大值\(s[i]\)所以每次求出\(dp[i]\)的时候更新\(S[i]\)和\(s[i]\)，然后就可以\(O(1)\)查询了，总时间复杂度\(O(n\sqrt{n})\)

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxm=330;
int N,F[maxn],a[maxn],b[maxn];
int tot,c[maxn],M[maxm],m[maxn],max_x;
int st[maxm],ed[maxm],bel[maxn],Ans,sq;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void updata(int x,int val){
	for(int j=x;j<=ed[bel[x]];j++)m[j]=max(m[j],val);
	for(int j=bel[x];j<=sq;j++)M[j]=max(M[j],val);
	
}
int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++){a[i]=read();max_x=max(max_x,a[i]);}
	sq=sqrt(max_x);
	for(int i=1;i<=sq;i++){
		st[i]=max_x/sq*(i-1)+1;
		ed[i]=max_x/sq*i;
	}ed[sq]=max_x;
	for(int i=1;i<=sq;i++)
		for(int j=st[i];j<=ed[i];j++)
			bel[j]=i;
	memset(M,128,sizeof M);
	memset(m,128,sizeof m);
	updata(a[1],0);
	for(int i=2;i<=N;i++){
		F[i]=F[i-1];
		for(int l=1,r=0;l<=a[i];l++){r=min(a[i]/(a[i]/l),a[i]);int ret=max(M[bel[r]-1],m[r]);F[i]=max(F[i],ret+(a[i]/r));l=r;}
		if(F[i]>m[a[i]]){
			updata(a[i],F[i]);
		}
	}
	printf("%d\n",F[N]);
	return 0;
}