Ananimous(2) 找出得分最高的无重复子段

回复 20# vvnesaa
额，这个不好这么说吧，因为元素是在不断加入进来的，每次必须以logn的复杂度来维护才能不影响整体的复杂度，如果每次都排序不就变成n*nlogn了，每次直接插入新元素也会使复杂度变为n^2。所以我觉得第一个堆应该是非常必要的


   

对的～
那个插入顺序。。。
你这么想：
[1, 5], [2, 3]算好了，现在要算[4, 6]
那么按end从小到大排，[ ...
vvnesaa 发表于 2011-4-20 10:23

MM是不是想复杂了，下面是我的思路，DP,无需而外空间（非极端情况下是nLogn时间，O(1)空间）：

Sort the segments by  ending points says B
Look for B from beginning to the end, for each new segment, decide whether to add
it or not. TotalScore(n) = max{TotalScore(n-1), TotalScore(m)+Score(n)}, m is the
max number that do not overlapped with nth segment which means m+1 to n-m are overlapped with n(th) segment

极端情况时间复杂度是n^2,就是n个段互相重合

回复  vvnesaa
额，这个不好这么说吧，因为元素是在不断加入进来的，每次必须以logn的复杂度来维护才能不 ...
darksteel 发表于 2011-4-20 10:46

囧。。。不好意思偶说错了。。。
根本不需要我说的那个堆。。。
直接记可能的最大值就好了@@
我太弱了。。。。@@

回复 22# wwwyhx
感觉这个和dp有点类似，如果dp的时候按end从小到大排序，应该就是你这个意思。我再想如果你找m的时候用上二分，是不是可以降到nlogn呢？那位MM的方法我终于弄明白了，也是相当巧妙的

   

回复 23# vvnesaa
啊！是这样，没错没错，原来你说的那一个堆就是指维护end的堆，这下全清楚了。。哪里，我感觉您编程和思维能力都很强，周围很少有这么厉害的女生。绝没有瞧不起女生的意思，只不过女生一般涉及coding都会有点头痛

   

MM是不是想复杂了，下面是我的思路，DP,无需而外空间（非极端情况下是nLogn时间，O(1)空间）：

Sort ...
wwwyhx 发表于 2011-4-20 11:32

我也是这样理解的. 那么如何找到max m使得m.end < n.start? 线性查找的话平均case总时间是O(n^2), 如果用二分查找在1 to n-1 里面查找的话, 平均case和极端case的时间可以变为O(nlogn)   不知道这样分析和理解对不对, 代码稍后发上.

1. 
   
2. sort(sortStart.begin(), sortStart.end(), [](int a, int b) { return seg[a].start < seg[b].start; } );
   
3. sort(sortEnd.begin(), sortEnd.end(), [](int a, int b) { return seg[a].end < seg[b].end; } );
   
4. 
   
5. f[0] = 0;
   
6. for (int i = 1, j = 1, maxf = 0; i <= n; ++i)
   
7. {
   
8.     while (j < i && seg[sortEnd[j]].end < seg[sortStart[i]].start)
   
9.     {
   
10.         if (f[j] > maxf)    maxf = f[j];
    
11.         ++j;
    
12.     }
    
13.     f[i] = max(f[i - 1], maxf + seg[sortStart[i]].score);
    
14. }
    

复制代码

我也是这样理解的. 那么如何找到max m使得m.end < n.start? 线性查找的话平均case总时间是O(n^2), 如果 ...
Imbalism 发表于 2011-4-20 12:03

这个找m就是直接往后找就可以啦，如果新段覆盖的范围大就多找点，当然不嫌麻烦还是可以用二分，不过我觉得到这一步就够了。O(n^2)是极端的情况，平均时间复杂度因该还是nlogn。就像我们说的快速排序，说时间复杂度是O(nlogn)指的也是平均时间复杂度，最坏情况下快速排序时间复杂度还是O(n^2)

囧。。。不好意思偶说错了。。。
根本不需要我说的那个堆。。。
直接记可能的最大值就好了@@
我太弱 ...
vvnesaa 发表于 2011-4-20 11:55

这个MM还是很厉害的，大家记住他的ID

我的代码， 方法如前楼所述

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. #include <limits>
   
5. #include <assert.h>
   
6. using namespace std;
   
7. 
   
8. 
   
9. const int MIN = numeric_limits<int>::min();
   
10. 
    
11. 
    
12. struct Node
    
13. {
    
14.      int start;
    
15.      int end;
    
16.      int value;
    
17. };
    
18. 
    
19. 
    
20. bool compare(const Node& a, const Node& b)
    
21. {
    
22.      return a.end < b.end;
    
23. }
    
24. 
    
25. 
    
26. int max(int a, int b)
    
27. {
    
28.      return a > b ? a : b;
    
29. }
    
30. 
    
31. 
    
32. 
    
33. 
    
34. //if t is not found in the array a
    
35. //return the index of nearest element
    
36. //that is smaller than t
    
37. int binarySearch(vector<Node> &a, int l, int u, int t)
    
38. {
    
39.      while(true)
    
40.      {
    
41. 
    
42.   int m = (l + u + 1) / 2;
    
43. 
    
44.   if(a[m].end == t)
    
45. 
    
46.        return m;
    
47. 
    
48.   if(a[m].end < t)
    
49. 
    
50.   {
    
51. 
    
52.        //t is in (m + 1, u)
    
53. 
    
54.        l = m + 1;
    
55. 
    
56.        if (l > u)
    
57. 
    
58.     assert(a.end < t);
    
59. 
    
60.     return u;
    
61. 
    
62.   }
    
63. 
    
64.   if(a[m].end > t)
    
65. 
    
66.   {
    
67. 
    
68.        //t is in (l, m - 1)
    
69. 
    
70.        u = m - 1;
    
71. 
    
72.        if(l > u)
    
73. 
    
74.     assert(a[l].end < t);
    
75. 
    
76.     return l;
    
77. 
    
78.   }
    
79.      }
    
80. }
    
81. 
    
82. 
    
83. int maxSum(vector<Node> &a)
    
84. {
    
85.      //dummy node for coding convenience
    
86.      Node dummyMin = {MIN, MIN, 0};
    
87.      a.push_back(dummyMin);
    
88.      sort(a.begin(), a.end(), compare);
    
89.      int *dp = new int[a.size()];
    
90.      dp[0] = 0;
    
91.      for (int i = 1; i < a.size(); ++i)
    
92.      {
    
93. 
    
94.   //if i is not in the optimized solution
    
95. 
    
96.   int v1 = dp[i - 1];
    
97. 
    
98.   //if i is in the optimized solution
    
99. 
    
100.   int k = binarySearch(a, 0, i - 1, a.start);
     
101. 
     
102.   assert(k < i && k >= 0);
     
103. 
     
104.   assert(a[k + 1].end > a.start && a[k].end <= a.start);
     
105. 
     
106.   int v2 = dp[k] + a.value;
     
107. 
     
108.   //find the max of two cases
     
109. 
     
110.   dp = max(v1, v2);
     
111. 
     
112.   assert(dp >= dp[i - 1]);
     
113.      }
     
114.      int r = dp[a.size() - 1];
     
115.      delete[] dp;
     
116.      return r;
     
117. }
     
118. #include <iostream>
     
119. #include <algorithm>
     
120. #include <vector>
     
121. #include <limits>
     
122. #include <assert.h>
     
123. using namespace std;
     
124. 
     
125. 
     
126. const int MIN = numeric_limits<int>::min();
     
127. 
     
128. 
     
129. struct Node
     
130. {
     
131.      int start;
     
132.      int end;
     
133.      int value;
     
134. };
     
135. 
     
136. 
     
137. bool compare(const Node& a, const Node& b)
     
138. {
     
139.      return a.end < b.end;
     
140. }
     
141. 
     
142. 
     
143. int max(int a, int b)
     
144. {
     
145.      return a > b ? a : b;
     
146. }
     
147. 
     
148. 
     
149. 
     
150. 
     
151. //if t is not found in the array a
     
152. //return the index of nearest element
     
153. //that is smaller than t
     
154. int binarySearch(vector<Node> &a, int l, int u, int t)
     
155. {
     
156.      while(true)
     
157.      {
     
158. 
     
159.   int m = (l + u + 1) / 2;
     
160. 
     
161.   if(a[m].end == t)
     
162. 
     
163.        return m;
     
164. 
     
165.   if(a[m].end < t)
     
166. 
     
167.   {
     
168. 
     
169.        //t is in (m + 1, u)
     
170. 
     
171.        l = m + 1;
     
172. 
     
173.        if (l > u)
     
174. 
     
175.     assert(a.end < t);
     
176. 
     
177.     return u;
     
178. 
     
179.   }
     
180. 
     
181.   if(a[m].end > t)
     
182. 
     
183.   {
     
184. 
     
185.        //t is in (l, m - 1)
     
186. 
     
187.        u = m - 1;
     
188. 
     
189.        if(l > u)
     
190. 
     
191.     assert(a[l].end < t);
     
192. 
     
193.     return l;
     
194. 
     
195.   }
     
196.      }
     
197. }
     
198. 
     
199. 
     
200. int maxSum(vector<Node> &a)
     
201. {
     
202.      //dummy node for coding convenience
     
203.      Node dummyMin = {MIN, MIN, 0};
     
204.      a.push_back(dummyMin);
     
205.      sort(a.begin(), a.end(), compare);
     
206.      int *dp = new int[a.size()];
     
207.      dp[0] = 0;
     
208.      for (int i = 1; i < a.size(); ++i)
     
209.      {
     
210. 
     
211.   //if i is not in the optimized solution
     
212. 
     
213.   int v1 = dp[i - 1];
     
214. 
     
215.   //if i is in the optimized solution
     
216. 
     
217.   int k = binarySearch(a, 0, i - 1, a.start);
     
218. 
     
219.   assert(k < i && k >= 0);
     
220. 
     
221.   assert(a[k + 1].end > a.start && a[k].end <= a.start);
     
222. 
     
223.   int v2 = dp[k] + a.value;
     
224. 
     
225.   //find the max of two cases
     
226. 
     
227.   dp = max(v1, v2);
     
228. 
     
229.   assert(dp >= dp[i - 1]);
     
230.      }
     
231.      int r = dp[a.size() - 1];
     
232. 
     
233. int main(int argc, char *argv[])
     
234. {
     
235.      vector<Node> a = {{1, 3, 3}, {2, 3, 100}, {0, 4, 2}, {3,5, 7}, {2, 6,1}, {0, 6, 2}, {2, 6, 1}, {6, 7, 3}};
     
236.      cout << maxSum(a) << endl;
     
237.      return 0;
     
238. }

复制代码