Cow Jog G

    技术2022-07-13  61

    题目链接:Cow Jog G


    显然我们只和第一个位置,和最后的位置有关。速度其实无所谓。

    然后就变成一个一个序列的最少LIS划分数,根据dirworth定理,也就是最长反链。


    AC代码:

    #pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int n,t,a[N],d[N],cnt; signed main(){ cin>>n>>t; for(int i=1,b,c;i<=n;i++) scanf("%lld %lld",&b,&c),a[i]=b+c*t; for(int i=n;i>=1;i--){ if(!cnt||a[i]>=d[cnt]) d[++cnt]=a[i]; else d[upper_bound(d+1,d+1+cnt,a[i])-d]=a[i]; } cout<<cnt; return 0; }
    Processed: 0.021, SQL: 9