自动搬运

查看原文

来自洛谷，原作者为

	xiaoliebao1115 real life

搬运于2025-08-24 23:02:10，当前版本为作者最后更新于2024-08-16 19:44:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

小清新双向搜索题，难度比卖瓜稍难吧。

idea

双向搜索

看到 $n\le 40$，很容易想到把整个序列分成两半进行搜索。

对于左半边搜索，每个点枚举经过和不经过。搜索到最后记录这次搜索的总金币数以及最后一个经过的位置的高度 $h_i$。

对于右半边搜索，记录的是第一个经过的位置的高度 $h_j$，其他和左半边搜索一样。

我们把左半边搜索的总金币数记为 $g_i$，右边记为 $g_j$。

二维偏序

根据题目要求的限制可以得出：$h_i\le h_j$，还有 $k\le g_i+g_j$，可以化为 $k-g_i\le g_j$，明显变成了一个二维偏序的形式，使用树状数组求解即可。

具体的，把所有搜索得到的结果都存入一个结构体数组中，先对 $k-g_i$ 和 $g_j$ 进行离散化，再按照 $h_i$ 排序。

对于左边搜到的，将 $k-g_i$ 加入树状数组，否则答案加上树状数组中所有小于等于 $g_j$ 的数的数量即可。

code

const int nn=41,mm=(1<<20)+5,kk=1e9,hyf=1<<21;//膜拜hhhyyyfff大佬
int n,h[nn],cnt;
ll g[nn],k,ans;
int tree[mm<<1];
inline void add(int x){//树状数组
	for(int i=x;i<=hyf;i+=i&(-i)) tree[i]++;
}
inline int query(int x){
	int tot=0;
	for(int i=x;i>=1;i-=i&(-i)) tot+=tree[i];
	return tot;
}
struct node{
	int h,tp;
	ll g;
};
node x[mm<<1];
inline bool cmp(node l1,node l2){
	return l1.g<l2.g;
}
inline bool cmp2(node l1,node l2){
	if(l1.h==l2.h) return l1.tp<l2.tp;
	return l1.h<l2.h;
}
inline void dfs(int wz,ll sum,int lst){
	if(wz>n/2){
		cnt++;
		x[cnt].h=lst,x[cnt].g=k-sum>0?k-sum:0;
		return ;
	}
	if(lst<=h[wz]) dfs(wz+1,sum+g[wz],h[wz]);
	dfs(wz+1,sum,lst);
}//搜索左边
inline void dfs2(int wz,ll sum,int lst){
	if(wz<=n/2){
		cnt++;
		x[cnt].h=lst,x[cnt].g=sum,x[cnt].tp=1;
		return ;
	}
	if(lst>=h[wz]) dfs2(wz-1,sum+g[wz],h[wz]);
	dfs2(wz-1,sum,lst);
}//搜索右边
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>h[i]>>g[i];
	dfs(1,0,0);
	dfs2(n,0,kk);
	sort(x+1,x+cnt+1,cmp);
	int mzhxi=0;
	ll prvg=-1,bfg;
	for(int i=1;i<=cnt;i++){
		bfg=x[i].g;
		if(x[i].g==prvg) x[i].g=mzhxi;
		else x[i].g=++mzhxi;
		prvg=bfg;//离散化
	}
	sort(x+1,x+cnt+1,cmp2);
	for(int i=1;i<=cnt;i++){
		if(x[i].tp){
			ll sum=query(x[i].g);
			ans+=sum;
		}
		else add(x[i].g);
	}
	cout<<ans<<endl;
	return 0;
}

时间复杂度 $O(2^{\frac n 2}\log2^{\frac n 2})$。