/**//* 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.cppblog.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
搜索
最新评论
|
|