自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 22:16:06，当前版本为作者最后更新于2024-04-23 17:39:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像是我初二的时候提出的一个问题，当时 u 群有人说存在 $O(n^23^{n/3})$ 做法，昨天晚上突然会做了！

考虑从前往后 DP，暴力是记录 $S$ 表示目前选择的数的集合，这样状态数仍然是 $O(2^n)$ 级别。

但我们注意到，设 $i$ 后面的数分别为 $x_1,x_2,\cdots,x_k$，我们只关心 $[1,x_1),(x_1,x_2),\cdots,(x_k,n]$ 这些每一段中选了多少个数。于是状态数不会超过每段长度 $+1$ 的乘积，由柯西不等式可以知道一定在段长相同时取到最值，直接看成连续的情况来分析，简单求导可以得到最值在 $e^{n/e}$，由于问题是离散的于是最值大约是 $3^{n/3}$。

于是直接 DP 就可以了。时间复杂度是 $O(n^23^{n/3})$，使用 map 或许会被卡常，手写哈希表可以稳过。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int N=41;
const int M=(1<<22);
const int P=47;
int a[N],n;

struct HashMap{

pair<int,ll>vals[M];
vector<int>havs;
vector<int>act[M];

int head[M],nxt[M],tot;
int size(){return tot;}
void clear(){
	for(int i=1;i<=tot;i++)nxt[i]=0,vector<int>().swap(act[i]);
	for(int i:havs)head[i]=0;
	vector<int>().swap(havs),tot=0;
}
void Ins(vector<int>&A,pair<int,ll>val){
	int res=0;
	for(int x:A)res=(((res*P)+x+1)&(M-1));
	
	int p=head[res];
	if(!p)p=++tot,act[p]=A,vals[p]=val,havs.emplace_back(res),head[res]=p;
	else{
		while(act[p]!=A&&p)p=nxt[p];
		if(!p)p=++tot,act[p]=A,vals[p]=val,nxt[p]=head[res],head[res]=p;
		else{
			if(vals[p].fi==val.fi)vals[p].se+=val.se;
			else if(vals[p].fi>val.fi)vals[p]=val;
		}
	}
}

};

HashMap f[2];

signed main(void){

	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	
	int cur=0;
	vector<int>NaganoharaYoimiya(n+1,0);
	f[0].Ins(NaganoharaYoimiya,mk(0,1ll));

	for(int i=1;i<=n;i++){
		vector<int>x;f[cur^1].clear();
		for(int j=i;j<=n;j++)x.emplace_back(a[j]);
		sort(x.begin(),x.end());int p=0;
		for(int j=0;j<x.size();j++)if(x[j]==a[i])p=j;

		for(int _=1;_<=f[cur].tot;_++){
			auto A=f[cur].vals[_];
			int w=A.fi;ll cc=A.se;
			int nw=0;for(int j=p+1;j<f[cur].act[_].size();j++)nw+=f[cur].act[_][j];
			auto to=f[cur].act[_];int cnt=to[p]+to[p+1];
			to.erase(to.begin()+p);
			to[p]=cnt,f[cur^1].Ins(to,mk(w,cc));
			to[p]=cnt+1,f[cur^1].Ins(to,mk(w+nw,cc));
		}
		
		cur^=1;
	}

	vector<pair<int,ll> >ans(n+1);
	for(int i=1;i<=f[cur].tot;i++){
		auto vec=f[cur].act[i];auto A=f[cur].vals[i];
		assert(vec.size()==1);
		int cnt=vec[0];
		ans[cnt]=A;
	}
	
	for(int i=1;i<=n;i++)cout<<ans[i].fi<<" "<<ans[i].se<<endl;

	return 0;
}