首页 > 代码库 > HDU4742----Pinball Game 3D（三维LIS、CDQ分治）
HDU4742----Pinball Game 3D（三维LIS、CDQ分治）
题意：三维空间内 n个小球，对应坐标（x,y,z）。输出LIS的长度以及方案数。
首先可以先按x排序，先降低一维，然后 剩下y 、z，在y上进行CDQ分治，按y的大小用前面的更新后面的。z方向离散化之后用树状数组维护就可以了。
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 1e5+10; 20 const int mod = 1 << 30; 21 struct Ball 22 { 23 int x,y,z,idx; 24 bool operator < (const Ball &rhs)const 25 { 26 return x < rhs.x || (x == rhs.x && y < rhs.y) || (x == rhs.x && y == rhs.y && z < rhs.z); 27 } 28 } ball[maxn],tmpball[maxn]; 29 struct DP 30 { 31 int len,cnt; 32 DP(){} 33 DP(int _len,int _cnt): 34 len(_len),cnt(_cnt) {} 35 } dp[maxn],c[maxn]; 36 int vec[maxn],idx; 37 inline int lowbit (int x) 38 { 39 return x & -x; 40 } 41 inline void update (DP &dp1, DP &dp2) 42 { 43 if (dp1.len < dp2.len) 44 dp1 = dp2; 45 else if (dp1.len == dp2.len) 46 dp1.cnt += dp2.cnt; 47 } 48 inline void modify(int x,DP &d) 49 { 50 while (x <= idx) 51 { 52 update(c[x],d); 53 x += lowbit(x); 54 } 55 } 56 DP query(int x) 57 { 58 DP ans = DP (0,0); 59 while (x) 60 { 61 update(ans,c[x]); 62 x -= lowbit(x); 63 } 64 return ans; 65 } 66 inline void CLR(int x) 67 { 68 while (x <= idx) 69 { 70 c[x] = DP(0,0); 71 x += lowbit(x); 72 } 73 } 74 void CDQ (int l, int r) 75 { 76 if (l == r) 77 return ; 78 int mid = (l + r) >> 1; 79 CDQ (l, mid); 80 for (int i = l; i <= r; i++) 81 { 82 tmpball[i] = ball[i]; 83 tmpball[i].x = 0; 84 } 85 sort(tmpball+l,tmpball+r+1); 86 for (int i = l; i <= r; i++) 87 { 88 if (tmpball[i].idx <= mid) 89 { 90 modify(tmpball[i].z,dp[tmpball[i].idx]); 91 } 92 else 93 { 94 DP tmp = query(tmpball[i].z); 95 tmp.len++; 96 update(dp[tmpball[i].idx],tmp); 97 } 98 } 99 for (int i = l; i <= r; i++)100 {101 if (tmpball[i].idx <= mid)102 {103 CLR(tmpball[i].z);104 }105 }106 CDQ (mid+1, r);107 }108 int main(void)109 {110 #ifndef ONLINE_JUDGE111 freopen("in.txt","r",stdin);112 #endif113 int T, n;114 scanf ("%d",&T);115 while (T--)116 {117 scanf ("%d",&n);118 for (int i = 1; i <= n; i++)119 {120 scanf ("%d%d%d",&ball[i].x, &ball[i].y, &ball[i].z);121 vec[i-1] = ball[i].z;122 }123 sort (ball+1, ball+n+1);124 sort (vec,vec+n);125 idx = unique(vec,vec+n) - vec;126 for (int i = 1; i <= n ; i++)127 {128 ball[i].z = lower_bound(vec,vec+idx,ball[i].z) - vec + 1;129 ball[i].idx = i;130 dp[i] = DP(1,1);131 }132 CDQ(1,n);133 DP ans = DP(0,0);134 for (int i = 1; i <= n ;i++)135 {136 update(ans,dp[i]);137 }138 printf("%d %d\n",ans.len, ans.cnt % mod);139 }140 return 0;141 }
HDU4742----Pinball Game 3D（三维LIS、CDQ分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。