中石油训练赛 - Racing Gems(最长不下降子序列)

题目描述

You  are  playing  a  racing  game.  Your  character  starts  at  the  X-axis  line  (y=0)  and proceeds up the racetrack, which has a boundary at the line x=0 and x=w.  The finish is at  y=h,  and  the  game  ends  when  you  reach  that  line.    You  proceed at a  fixed vertical velocity v, but you can control your horizontal velocity to be any value between -v/r and v/r,  where  r  is  a  fixed  ratio.  You  may  change  your  horizontal velocity at any time, but your vertical velocity must remain fixed. 
There are gems at specific points on the race track. Your job is to collect as many gems as possible (they all have the same value). 
How many gems can you collect? You may start at any horizontal position you want (but your vertical position must be 0 at the start).

输入

Each input will consist of a single test case. Note that your program may be run multiple times  on  different  inputs.  The  first  line  will  contain  four  integers:  n  (1≤n≤105 )  is  the number  of  gems,  r  (1≤r≤10)  is  the  ratio  of  vertical  velocity  to  maximum  horizontal speed, w (1≤w≤109 ) is the width of the track, and h (1≤h≤109 ) is the height of the finish line.    Following  this  will  be  n  lines,  each  containing  an  integer  x  and  y  coordinate 
(0≤x≤w,1≤y≤h), containing the coordinate of a gem.  All gems will lie on the race track.  None will be on the start line.   

输出

Output  a  single  integer  on  a  line  by  itself  representing the maximum number of gems that you can collect.

样例输入

5 1 10 10
8 8
5 1
4 6
4 7
7 9

样例输出

3

题目链接：点击查看

---

题目大意：一个在二维坐标平面开展的跑车游戏，首先规定赛道边界：左右边界分别为x=0和x=w，上下边界分别为y=0和y=h，现在要求从y=0跑到y=h，现在规定一个速度比率，也就是，在路上有许多宝石，我们需要尽可能多的去吃到宝石，问我们最后到达终点的时候，吃到宝石数的最大值是多少？

题目分析：这个题目我们算是分析了好久好久吧，先从网上拿来一张图，更好理解一下这个题目：

一开始我们大概就分析到了这个地方，先给宝石对于纵坐标排序，然后可以设一个dp[i]代表在吃到宝石i的情况下获得的最大值，那么我们很轻松就能看出来，dp[i]=max(dp[i],dp[j]+1)（1<=j<i） ，也就是我们需要在前i-1个宝石中寻找满足斜率条件的最大值，但这样一来时间复杂度就变为了n*n，对于这个题目而言不可行，后来我们讨论了半天，最后终于得出了结论（%yh学长），就是将rate当一个斜率来看待，有了每一个点和斜率了，就可以求出直线方程，然后求出对于x=0和x=w的交点纵坐标，就像上图一样，因为每个宝石所构成的一个带角度的范围内的其余宝石，才能接受当前宝石的状态转移，这个应该不难想到，随后我们对于任意一边的坐标升序排序，然后对于另一边的坐标找一下最长不下降子序列即可

代码：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
using namespace std;
  
typedef long long LL;
  
const int inf=0x3f3f3f3f;
  
const int N=1e5+100;
 
struct Node
{
    LL x,y;
    bool operator<(const Node& a)const
    {
        return x<a.x;
    }
}a[N];
 
LL d[N];
  
int main()
{
//  freopen("input.txt","r",stdin);
    LL n,rate,w,h;
    scanf("%lld%lld%lld%lld",&n,&rate,&w,&h);
    for(int i=1;i<=n;i++)
    {
        LL x,y;
        scanf("%lld%lld",&x,&y);
        a[i].x=rate*x+y;
        a[i].y=rate*(w-x)+y;
    }
    sort(a+1,a+1+n);
    int len=1;
    memset(d,0,sizeof(d));
    d[1]=a[1].y;
    for(int i=2;i<=n;i++)
    {
        if(a[i].y>=d[len])
        {
            d[++len]=a[i].y;
        }
        else
        {
            int j=upper_bound(d+1,d+1+len,a[i].y)-d;
            d[j]=a[i].y;
        }
    }
    cout<<len<<endl;
     
     
     
     
     
     
     
     
      
      
      
      
      
      
      
    return 0;
}