D - プレゼント AtCoder Beginner Contest 038

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder

問題概略

x,yでの最大部分増加列

制約

• 1≦N≦10⁵
• 1≦h_i≦10⁵
• 1≦w_i≦10⁵

解法１

dp[i] := 　iまでを使ってできる最長の増加列。

1次元の場合はソートして、一つ一つ見ていき小さい場合は自分より大きい最小の番目を小さく更新でき、誰よりも大きい場合は新しい長さを獲得する。

2次元の場合、x,yについて昇順にソートすると1 2,1 3 のような時に長さが2であると判定されてしまう。これを打開するにはyは降順にソートすれば良い。

そうすればlisとして解ける。

1. int main() {
2. //test();return 0;
3. int N = in();
4. vp p(N);
5. npa(p);
6. rep(i,N)p[i].S *= -1;
7. vsort(p);
8. vi a(N);
9. rep(i,N)a[i] = -p[i].S;
11. vi dp(N+3,INF);
12. rep(i,N){
13. *lower_bound(vall(dp),a[i]) = a[i];
14. }
15. cout << lower_bound(vall(dp),INF) - dp.begin()<< endl;
16. return 0;
17. }

解法２

dpi[i] := iを一番外側とした時にできる最長

iより小さい箱jでdp[i] =  max(dp[j]) + 1となる。

1のようにソートしたとき、同じように入れ子にならない。

public static void main(String[] args)
{
    //longを忘れるなオーバーフローするぞ
    N = sc.nextInt();
    P[] p = new P[N];
    for (int i = 0; i < N; i++)
    {
        p[i] = new P(sc.nextInt(), -sc.nextInt());
    }
    Arrays.sort(p);
    int S = 123456;
    SegmentTree st = new SegmentTree(S);
    for (int i = 0; i < N; i++)
    {
        st.update(-p[i].y, st.queryMax(0, -p[i].y) + 1);
    }
    System.out.println(st.queryMax(0, S));

}