前幾天就解出來了 不過忘記丟了
雖然不是自己解的(((
總之把每個娃娃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的顏色ˊ_>ˋ
沒有留言:
張貼留言