P4165 [SCOI2007]组队 题解

$\color{deeppink}link$

考试时 DS 写挂了，导致保龄。。

看到有 $\min$ 以及只有 $5000$ 的 $N$，可以自然的想到枚举最小值来求答案。

假设我们枚举的 $minH$ 是 $i$，$minV$ 是 $j$ （注意 $height_i\le height_j,speed_j\le speed_i$），那么如果有一个 $k$ 可以被选入，则它满足一下条件：

• $speed_j\le speed_k$
• $height_i\le height_k$
• $A(height_k-height_i)+B(speed_k-speed_j)\le C$

我们尝试把第三个化简一下：

$A*height_k+B*speed_k-A*speed_i-B*speed _j\le C$

$A*height_k+B*speed_k\le C+A*speed_i+B*speed _j$

可以看到，后面值已经确定，前面的值只与 $k$ 有关。

把三个限定条件摆到一起：这不就是 三维偏序 吗？剩下的都是板子。写什么都行，可就我写的是线段树套线段树，跑得贼慢。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+350,M=1e4,I=1e6+500;

struct node
{
	int h,s;
	
	friend bool operator<(node a,node b)
	{
		return a.h==b.h?a.s>b.s:a.h<b.h;
	}
}a[N];

int n,ans,jk,tot,ls[I],rs[I],val[I];
int A,B,C,re[N],o[N];
map<int,int>mp;

class tree_and_tree
{
	public:
		int ro;
		
		#define mid ((l+r)>>1)
		
		void pre(int&x){x=++tot;}
		
		void insert(int x,int l,int r,int t)
		{
			val[x]++;
			if(l==r)return;
			if(!ls[x])pre(ls[x]);
			if(!rs[x])pre(rs[x]);
			if(t<=mid)insert(ls[x],l,mid,t);
			else insert(rs[x],mid+1,r,t);
			return;
		}
		
		int query(int x,int l,int r,int L,int R)
		{
			if(L>R)return 0;
			if(!x)return 0;
			if(L<=l&&R>=r)return val[x];
			int ans=0;
			if(L<=mid)ans+=query(ls[x],l,mid,L,R);
			if(R>mid)ans+=query(rs[x],mid+1,r,L,R);
			return ans;
		}
}t[M<<3];

int find(int x,int l,int r,int L,int R,int y)
{
	if(L<=l&&R>=r)return t[x].query(t[x].ro,1,jk,1,y);
	int tmid=(l+r)>>1,ans=0;
	if(L<=tmid)ans+=find(x<<1,l,tmid,L,R,y);
	if(R>tmid)ans+=find(x<<1|1,tmid+1,r,L,R,y);
	return ans;
}

int get(int mins,int mxre)
{
	int l=upper_bound(o+1,o+1+jk,mxre)-o-1;
	return find(1,1,M,mins,M,l);
}

void insert(int x,int l,int r,int a,int b)
{
	t[x].insert(t[x].ro,1,jk,b);
	if(l==r)return;
	int tmid=(l+r)>>1;
	if(a<=tmid)insert(x<<1,l,tmid,a,b);
	else insert(x<<1|1,tmid+1,r,a,b);
}

main()
{
	for(int i=1;i<=(M<<2);i++)t[i].ro=++tot;
	cin>>n>>A>>B>>C;
	for(int i=1;i<=n;i++)cin>>a[i].h>>a[i].s;sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)re[i]=(A*a[i].h+B*a[i].s)-C,o[i]=re[i];
	sort(o+1,o+1+n);jk=unique(o+1,o+1+n)-o-1;
	for(int i=1;i<=jk;i++)mp[o[i]]=i;
	for(int i=n;i>=1;i--)//minH
	{
		insert(1,1,M,a[i].s,mp[re[i]]);
		for(int j=i;j<=n;j++)//minS
		if(a[j].s<=a[i].s)
		{
			int p=A*a[i].h+B*a[j].s;
			if((re[i]>p)||(re[j]>p))continue;
			int x=get(a[j].s,p);
			ans=max(ans,x);
		}
	}
	cout<<ans;
}