予鈴

競プロとか備忘録とか…

ABC038 D - プレゼント

問題概要

D - プレゼント

解く前に考えていたこと

AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がN \leq10^5O(N^2)解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にある N log N のLISを書くがWA
・途中でpair型dpを更新していた。

正解

まず前提として、プレゼントaがプレゼントbの中に梱包される条件とは、
 w_b>w_a \land h_b > h_a  が成立する必要がある。
したがって、wを昇順にソートして h に関してLISを考えればうまくいきそう。
ここで、pairでsortすると、同値のwに関して、hは昇順に並ぶこととなる。これが良くない。

i番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素はj番目( j < i)とする。
・このとき、w_i = w_jが成り立っていると、h_i < h_jとなっているため、上書きできない。(直感的に説明すると、j番目の要素の方がi番目の要素より条件が厳しい)

逆に言えば、w_i = w_jのときh_i > h_jとなっていれば、通常通り更新することができる。

#include<bits/stdc++.h>
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? 1e9:1e18)
using namespace std;
using pii = pair<int,int>;
auto f = [](pii a,pii b){
    return !((a.first == b.first and b.second> a.second) or a.first > b.first);
};
signed main(){
    int n; cin >> n;
    vector<pii>v(n);
    for(auto && e:v)cin >> e.first >> e.second;
    sort(all(v),f);
    vector<int>dp(n,INF),lis;
    for(auto && e:v)lis.emplace_back(e.second);
    rep(i,n){
        *lower_bound(all(dp),lis[i]) = lis[i];
    }
    cout << (int)(lower_bound(all(dp),INF)-dp.begin()) << endl;
}