題目鏈接

Racing Gems

You are playing a racing game. Your character starts at thex axis (y= 0) and PRoceeds up therace track, which has a boundary at the linex = 0 and another atx =w. You may start the raceat any horizontal position you want, as long as it is within the track boundary. The finish line isaty =h, and the game ends when you reach that line. You proceed at a fixed vertical velocityv,but you can control your horizontal velocity to be any value between?v/rand v/r, and change itat any time.

There are ngems at specific points on the race track. Your job is to collect as many gems aspossible. How many gems can you collect?

Input

The first line of input contains four space-separated integersn,r,w, andh (1≤ n≤ 105, 1 ≤ r≤ 10,1≤ w,h≤ 109). Each of the following nlines contains two space-separated integersxiand yi,denoting the coordinate of the ith gem (0≤ xi≤ w, 0< yi≤ h). There will be at most one gemper location.

The input does not include a value forv.Output

Print, on a single line, the maximum number of gems that can be collected during the race.

題意：

你在進行一場賽車，初始時你在(x, 0)位置，x屬于[0, w]。當到達y=h時，比賽結束。

有n個寶石，第i個寶石的坐標是(xi, yi)。不會有多個寶石在一個位置的情況。

若賽車的y方向的速度為v，那么x方向的速度在[-v/r, v/r]區間，速度可隨意調整。

現在不給出v，問最多能夠收集到多少寶石。

(1 <= n <= 1e5, 1 <= r <= 10, 1 <= w, h <= 1e9)。

(0 <= xi <= w, 0 <= yi <= h)。

n, r, w, h, xi, yi都為整形變量。

參考博客鏈接

題解：

把題目轉換一下就能發現，當賽車在某個位置時，它接下來能拾到的金幣的位置是跑道的位置和兩條射線夾的面積的相交部分。假如我們讓這兩條射線分別與賽道兩旁的邊界相交，那么就能得到兩個數字，分別記為a，b

最后我們能發現，本身是一個DAG模型，但是由于都很龐大，但是轉換成(a,b) 以后，如果想撿了這個金幣后還能撿到下一個金幣，那么就要保證下一個金幣的A比a大且B比b大，也可以相等。那么這就變成了一個二維無序LIS了，有一種很簡單的方法就是，把a從小到大排序，那么之后對b做最長不下降子序列，那么就是答案了。因為此時能保證a絕對不會下降。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const ll inf=1e18;const ll mod=1000000007;const int maxn=1e5+100;struct node{    ll a,b;    bool Operator <(const node& s)const{        return a<s.a;    }    node(ll x=0,ll y=0):a(x),b(y) {}}a[maxn];ll d[maxn];int main(){    int n,r,w,h;    while(~scanf("%d%d%d%d",&n,&r,&w,&h))    {        rep(i,1,n+1)        {            ll x,y;            scanf("%lld%lld",&x,&y);            a[i].a=1ll*x*r+y;            a[i].b=1ll*(w-x)*r+y;        }        sort(a+1,a+n+1);        fill(d,d+n,inf);        rep(i,0,n)        {            *upper_bound(d,d+n,a[i+1].b)=a[i+1].b;        }        printf("%d/n",lower_bound(d,d+n,inf)-d);    }    return 0;}