百团大战
Description
此百团大战非彼百团大战也。这指的是 HYSBZ 的社团开始招人了。若若的 LMZ 现在站在操场上，有很多很多个社团在操场上排成一排。有些社团为了吸引人们 加入，会表演节目。而现在 LMZ 拿到了节目单，有 n 个节目，其描述了在 Ti时 刻 Xi号社团会表演节目（持续时间忽略不计）。而 LMZ 在一单位时间内最多也只 能跑过 V 个社团的距离（比如从 1 号社团跑到 V+1 号社团），而最少则可以不动， 跑步的左右方向任意。他想知道：
当他初始时刻是站在 0 号社团的情况下，他最多能看到多少节目？
当他初始时刻可以站在任意位置的情况下，他最多能看到多少节目？
注：初始时刻指的是时间为 0.
Input
第一行仅 1 个正整数 n，为节目数量。
接下来 n 行每行 2 个正整数 Xi，Ti，为第 i 个节目的属性。
输入数据保证不会 有重复的节目。
最后一行一个正整数 V，表示 LMZ 的速度上限。
Output
仅 2 个正整数，分别为问题 1 和问题 2 的答案
Sample Input
3
6 1
1 3
4 4
4
Sample Output
2 3
思路：先按时间排序，假设在看第i个节目之前看了第j个节目，那么必须满足两个要求：1、(Ti-Tj)*v>=xi-xj；（i的位置比j后面）2、(Ti-Tj)*v>=xj=xi（i的位置在j前面） 然后把i移到一边，j移到一边，移项可得1、Ti*v-xi>=Tj*v-xj 2、Ti*v+xi>=Tj*v+xj
把Ti*v-xi和Ti*v+xi分别看成一个整体，即令它们分别等于f1,f2。看节目的顺序必须严格满足1、2两个不等式，所以我们可以先根据f1排序，使序列的f1是递增的，再对f2求不下降最长子序列，这样得到的长度就是同时满足1、2两个条件的最多观看节目（起始点从任意位置开始）
对于起点从0开始的情况，可以先对所有n个节目进行遍历，将所有f2<0（即在求最长不下降子序列过程中有可能代替0成为起点的节目，因为f2>=0的节目一定会在0之后再去观看）的点的f1变成-1，再对f1进行重新排序，这样所有f2<0的点都会在0点的前面，然后从0这个点开使找最长不下降子序列。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll;
struct node
{
int t,x,id;
ll f1,f2;
}p[100005];
ll dp[100005];
int n,v;
int fa[1000005];
bool cmp(node a,node b)
{
if(a.f1==b.f1)
return a.f2<b.f2;
return a.f1<b.f1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&p[i].x,&p[i].t);
p[i].id=i;
}
scanf("%d",&v);
for(int i=1;i<=n;i++)
{
p[i].f1=p[i].t*v-p[i].x;
p[i].f2=p[i].t*v+p[i].x;
}
sort(p+1,p+1+n,cmp);
ll len=1;dp[1]=p[1].f2;
for(int i=2;i<=n;i++)
{
if(p[i].f2>=dp[len])
{
len++; dp[len]=p[i].f2;
continue;
}
int j=upper_bound(dp+1,dp+1+len,p[i].f2)-dp;
dp[j]=p[i].f2;
}
p[0].id=0;p[0].f1=0;p[0].f2=0;
for(int i=1;i<=n;i++)
{
if(p[i].f2<0)
p[i].f1=-1;
}
sort(p,p+1+n,cmp);
int pos;
for(int i=0;i<=n;i++)
{
//printf("%d %lld\n",i,p[i].f1);
if(p[i].id==0)
{
pos=i;
break;
}
}
ll len2=1;
dp[1]=p[pos].f2;
for(int i=pos+1;i<=n;i++)
{
if(p[i].f2>=dp[len2])
{
len2++; dp[len2]=p[i].f2;
continue;
}
int j=upper_bound(dp+1,dp+1+len2,p[i].f2)-dp;
dp[j]=p[i].f2;
}
printf("%lld %lld\n",len2-1,len);
return 0;
}