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

|
|