题目链接: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;
}
转载请注明原文地址:https://ipadbbs.8miu.com/read-24062.html