学步园

3
-1 1
42 7
40 8
2

1 2

题目：http://codeforces.com/problemset/problem/76/F

题意：给你n个事件发生的事件和地点，在一条直线上，求最多可以见到几个事件。。。

分析：最直接的想法就是按时间排序，之后就可以简单的DP，这样明显是超时的，这种情况下，我们就得换种排序方式来改变数据的序，也改变转移方程。。。

一个点可以到达另一个点有个条件 abs(x[i]-x[j])<=abs(t[i]-t[j])*v

而这个不等式可以转换为 -x[ i ]+t[ i ]*v<=-x[ j ]+t[ j ]*v&&x[ i ]+t[ i ]*v<=x[ j ]+t[ j ]*v，为什么呢？

我们先假设t[ i ]<=t[ j ]，那么有 A：x[ i ]-x[ j ]<=(t[ j ]- t[ i ])*v (x[ i ]>=x[ j ])  B： x[ j ]-x[ i ]<=(t[ j ]- t[ i ])*v (x[ i ]<x[ j ])

仔细琢磨，发现x[ i ]>=x[ j ]的时候，有B式子一定满足，相反的A一定满足，所有只要AB同时满足，就说明可以到达

而t[ i ]> t[ j ]的情况与上面的情况类似，最后就推出上面的不等式。。。

知道上面的关系后，把每个事件，变成两个变量，a=-x[i ]+t[i]*v  b=x[i]+t[i]*v

按a排序，如果a相同，按b排序。。。然后就是LIS问题了

PS：高中没认真学数学，看来我真的错了T_T

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int mm=111111;
struct data
{
    long long p,q;
}g[mm];
long long q[mm],x[mm],t[mm],v;
int i,j,n,r,ans;
bool cmp(data a,data b)
{
    return a.p<b.p||(a.p==b.p&&a.q<b.q);
}
int find(int l,int r,long long x)
{
    int m,ret=0;
    while(l<=r)
    {
        m=(l+r)>>1;
        if(q[m]>x)ret=m,r=m-1;
        else l=m+1;
    }
    return ret;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;++i)
            scanf("%I64d%I64d",&x[i],&t[i]);
        scanf("%I64d",&v);
        for(i=0;i<n;++i)
        {
            g[i].p=-x[i]+t[i]*v;
            g[i].q=x[i]+t[i]*v;
        }
        sort(g,g+n,cmp);
        q[0]=-1e12,q[r=1]=1e12;
        for(i=0;i<n;++i)
        {
            j=find(0,r,g[i].q);
            if(q[j]>g[i].q)q[j]=g[i].q;
            if(j>=r)q[++r]=1e12;
        }
        ans=r-1;
        q[r=1]=1e10;
        for(i=0;i<n;++i)
            if(g[i].p>=0&&g[i].q>=0)
            {
                j=find(0,r,g[i].q);
                if(q[j]>g[i].q)q[j]=g[i].q;
                if(j>=r)q[++r]=1e12;
            }
        printf("%d %d\n",r-1,ans);
    }
    return 0;
}