https://www.acmicpc.net/problem/23035
문제를 읽어보면 가장 짧은 경로만 갈 수 있다니까 움직일 수 있는거리는 N+M이며 이는 문제에서 주어진 그림에서 상, 우 방향으로는 갈 수 없다는 소리다.
이를 유의해서 관점을 살짝 바꾸면 LIS 문제라는걸 쉽게 알 수 있다.
그럼 잘 풀면 된다.
pair에서의 LIS는 first에 대해 정렬을 한뒤 second에 대한 LIS를 구하면 자연스럽게 pair에 대한 LIS가 나온다.
참고로 LIS이지만 중복이 되는 LIS로 풀어야한다.
난 이거 안해서 삽질했다. ㅠ
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define INF 1e9
ll N,M,T,ans,rans;
vector< pair<ll,ll> > v,rv;
vector<ll> v2,rv2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>M;
cin>>T;
for(ll a,b,i=0;i<T;i++){
cin>>a>>b;
if(a<=N && b<=M){
v.push_back({a,b});
rv.push_back({a,b});
}
}
sort(v.begin(),v.end());
sort(rv.begin(),rv.end());
ll l = v.size();
v2.push_back(-INF);
for(ll i=0;i<l;i++){
if(v2.back()<=v[i].second){
v2.push_back(v[i].second);
ans++;
}else{
auto it = upper_bound(v2.begin(),v2.end(),v[i].second);
*it = v[i].second;
}
}
rv2.push_back(-INF);
for(ll i=0;i<l;i++){
if(rv2.back()<=rv[i].second){
rv2.push_back(rv[i].second);
rans++;
}else{
auto it = upper_bound(rv2.begin(),rv2.end(),rv[i].second);
*it = rv[i].second;
}
}
cout<<max(ans,rans);
return 0;
}```