【题目描述】
一年一度的星哥选美又拉开了帷幕
N个人报名参加选拔，每个人都有着各自的相貌参数和身材参数（不大于 10000 的正整数）。你的任务是尽可能让更多人被星哥选中，而唯一要求就是，在这只队伍里面的每个人，都需满足以下不等式：
A (H− h) +B(W− w) ≤ C
其中H和W为这个人的相貌和身材， h和w为选中者中的最小相貌参数和最小身材参数，而A、 B、 C为三个不大于10000 的正的整型常数。
现在请计算星哥最多可以选中多少人。
【输入格式】
第一行：一个整数： N(0<N<=2000)
第二行：三个分开的整数： A,B和C
第三行到第N+ 2行：每行有两个用空格分开的整数，分别表示一个人的相貌参数和身材参数
【输出格式】
第一行：最多被选的人数
【输入样例】
8
1 2 4
5 1
3 2
2 3
2 1
7 2
6 4
5 1
4 3
【输出样例】
5
其实也不全是DP，这里用到了一个数学的推导，实际就是个zz的不等式，
首先，固定一个h，而式子中A*(H-h)+B*(W-w)<=C -----> B*w>=A*H+B*W-C-A*h
明显w对于一个固定的人，有唯一的范围 (A*H+B*W-C-A*h)/B~w，每个人对应选这个h有一段w的范围，
因此对每个h就有选任一个w时能满足多少人，这样就是一个N^2加一点常数的效率，成功改良了N^3的暴力。。。
最终，对每个h,w选最大就行了。细节：H比h小的continue，可以考虑离散一下。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<ctime> #include<algorithm> using namespace std; int read() { int sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();} while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();} return sum*f; } struct peo { int a,b,id; } a[2005]; int n,ans=0,A,B,C,ha[2005],hb[2005],sza,szb,v[2005]; void init() { sort(ha+1,ha+n+1);sza=unique(ha+1,ha+n+1)-ha-1; sort(hb+1,hb+n+1);szb=unique(hb+1,hb+n+1)-hb-1; //sort(a+1,a+n+1,cmp); } int main() { // freopen("beauty.in","r",stdin); // freopen("beauty.out","w",stdout); n=read();A=read();B=read();C=read(); for(int i=1;i<=n;i++) { ha[i]=a[i].a=read(); hb[i]=a[i].b=read(); a[i].id=a[i].a*A+a[i].b*B-C; } init(); for(int i=1;i<=sza;i++) { int sum=0,t=ha[i]*A; memset(v,0,sizeof(v)); for(int j=1;j<=n;j++) { if(a[j].a<ha[i])continue; int g=(a[j].id-t)/B,l=upper_bound(hb+1,hb+szb+1,a[j].b)-hb; int k=lower_bound(hb+1,hb+szb+1,g)-hb; for(int h=k;h<=szb;h++) if(hb[h]<=a[j].b) v[h]++; else break; } for(int j=1;j<=szb;j++) sum=max(sum,v[j]); ans=max(ans,sum); } cout<<ans; }
