題目描述

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; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - Racing Gems(最长不下降子序列)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。