2016年9月13日 星期二

TIOJ 1907 俄羅斯娃娃

http://tioj.infor.org/problems/1907

前幾天就解出來了 不過忘記丟了
雖然不是自己解的(((

總之把每個娃娃w跟h搞成一個pair然後存起來
然後對那個vector(或是要用array也可以啦)sort
但是當wi==wj的時候hj>hi要在前面 然後wi<wj在前面 所以就自己炸一個cmp出來
然後再對h找LIS就過了

原本用了奇怪的方法優化+二分搜又寫爛一次-w-
看起來二分搜是我(眼前)最大的敵人(###

喔然後code因為有神奇優化過 所以沒用黑魔法(?



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<vector>
#include<stdio.h>
#include<utility>
#include<algorithm>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second

int n,w,h,i,t,tt;
char c;
vector<pii> rs,B;

inline int rit(){
    t=0;
    do{
        c=getchar_unlocked();
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar_unlocked();
    }while(c>='0'&&c<='9');
    return t;
};


bool cmp(const pii &a,const pii &b){
    if(a.X==b.X && a.Y>b.Y)return 1;
    return a.X<b.X;
}
bool cmpp(const pii &a,const pii &b){
    return a.Y<b.Y;
}

inline int LIS(){
    B.clear();
    B.push_back(rs[0]);
    for(i=1;i<n;i++){
        if(cmpp(B.back(),rs[i])){
            B.push_back(rs[i]);
        }
        else{
            *lower_bound(B.begin(),B.end(),rs[i],cmpp) = rs[i];
        }
    }
    return B.size();
}

int main(){
    tt=rit();
    while(tt--){
        n=rit();
        rs.clear();
        for(i=0;i<n;i++){
            w=rit();
            h=rit();
            rs.push_back({w,h});
        }
        sort(rs.begin(),rs.end(),cmp);
        printf("%d\n",LIS());
    }
}

.....我真的懶得改define跟include的顏色ˊ_>ˋ
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)