
 /**//*
n個事件,每個在時間ti(ti>=1),發生在坐標xi處, 人移動的速度是v
問當時間0時起始位置在0和起始位置任意選時最多能遇到的事件個數
n <= 100000
一開始我按照時間排序,然后就是從后往前dp[i] = max{dp[j]} + 1, tj >= ti && |xi-xj| <= v(tj-ti)
按照時間排后降了一維,能滿足tj>=ti,然后將|xi-xj| <= v(tj-ti)拆成xi+vti<=xj+vtj, xi-vti>=xj-vtj
以為能將xi+vti作為線段樹的軸,然后插入時是插入xi-vti,和dp[i],發現會有問題的,
主要是不同到兩個事件可能會有相同到xi+vti,這樣導致線段樹上到一個點有兩個值,更新時就不確定更新哪個了
這個處理跟2010福州的一題類似,通過對某個算出來的值排序降掉一維,然后再查找算出的另外一個值
http://www.shnenglu.com/Yuan/archive/2010/12/22/137176.html
以上掙扎后還是沒Gao出 .#_#
看了解題報告,不用對ti排序!!
因為我們是為了滿足|xi-xj| <= v(tj-ti),而滿足這個不等式的肯定有tj>=ti,所以不用對ti排序
以上不等式等價于: xi + vti <= xj + vtj , -xi + vti <= -xj + vtj
令p = xi + vti, q= -xi + vti,按照(p,q)排序,這樣就相當于找LIS了,比較的值是q
要用nlogn的LIS
題中的point0是指坐標為0,不是第一個事件的位置,下標是從1開始,顯然就不是啦(我一開是以為是 ..T_T)
還有一個地方就是,求LIS時注意=也是成立的!!!
很不錯的一道題吧,我一開始就陷入先對ti排序到困局..
如果能想到滿足|xi-xj| <= v(tj-ti)的必滿足tj>=ti就不用考慮ti了,轉去對p排序
*/
#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cassert>

using namespace std;

const long long INF = 1LL << 60;
const int MAXN = 100086;

 struct Event {
int t, x;
long long p, q;
// |xi - xj| <= v(tj-ti) , tj >= ti
//=> -v(tj-ti) <= xi - xj <= v(tj-ti) , don't need to consider tj >= ti . since this inequality implys
//=> -xi + vti <= -xj + vtj , xi + vti <= xj + vtj
// let p = x + vt q = -x + vt
// sort by (p,q)

void doit(long long v)
 {
p = x + v*t;
q = -x + v*t;
}

bool operator<(const Event & B)const
 {
 if (p != B.p) {
return p < B.p;
}
return q < B.q;
}

bool operator ==(const Event & B) const
 {
return x == B.x && t == B.t;
}
};

Event event[MAXN];
int dp[MAXN];

inline bool boundCmp(const int &a, const int &b)
  {
return event[a].q > event[b].q;
}

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
#endif

 for (int n, v, startX; ~scanf("%d", &n);) {

 for (int i = 0; i < n; i++) {
scanf("%d%d", &event[i].x, &event[i].t);
}
scanf("%d", &v);
 for (int i = 0; i < n; i++) {
event[i].doit(v);
}
sort(event, event + n);

int ans = 0;
vector<int> vt;
 for (int i = n - 1; i >= 0; i--) {
int pos = upper_bound(vt.begin(), vt.end(), i, boundCmp) - vt.begin();
dp[i] = pos + 1;
 if (pos == vt.size()) {
vt.push_back(0);
}
vt[pos] = i;
 if (abs(0 - event[i].x) <= (long long) v * event[i].t) {
ans = max(ans, dp[i]);
}
}
cout << ans << " " << *max_element(dp, dp + n) << endl;
}
return 0;
}

|
|
常用鏈接
隨筆分類
Links
搜索
最新評論

|
|