Differences From Artifact [13e543b5a0b1db44]:
- File
SRM/499-U/1B-U.cpp
- 2011-03-20 00:13:20 - part of checkin [2de557d8c0] on branch trunk - 499 (user: kinaba) [annotate]
- File
SRM/499/1B-U.cpp
- 2011-10-08 15:42:58 - part of checkin [b57cc94f1b] on branch trunk - Library for SCC added and verified. (user: kinaba) [annotate]
To Artifact [124c7549ad607d0d]:
- File
SRM/499/1B.cpp
- 2012-09-08 04:01:47 - part of checkin [109f2a9050] on branch trunk - 555 (user: kinaba) [annotate]
10 #include <iterator> 10 #include <iterator>
11 #include <functional> 11 #include <functional>
12 #include <complex> 12 #include <complex>
13 #include <queue> 13 #include <queue>
14 #include <stack> 14 #include <stack>
15 #include <cmath> 15 #include <cmath>
16 #include <cassert> 16 #include <cassert>
17 #include <cstring> <
18 using namespace std; 17 using namespace std;
19 typedef long long LL; 18 typedef long long LL;
> 19 typedef long double LD;
20 typedef complex<double> CMP; | 20 typedef complex<LD> CMP;
21 21
22 class WhiteSpaceEditing { public: 22 class WhiteSpaceEditing { public:
23 int getMinimum(vector <int> lines) 23 int getMinimum(vector <int> lines)
24 { 24 {
25 const int N = lines.size(); <
26 const int V = *max_element(lines.begin(), lines.end()); | 25 set<int> slen(lines.begin(), lines.end());
27 vector<int> dp(V+1), dp_neo(V+1); <
28 for(int v=0; v<=V; ++v) <
29 dp[v] = abs(v - lines[N-1]); <
30 for(int i=N-2; i>=0; --i) <
> 26 slen.insert(0);
31 { | 27
32 int best = INT_MAX; <
33 for(int v=lines[i]; v>=0; --v) { <
34 best = min(best, dp[v]); <
35 dp_neo[v] = abs(v - lines[i]) + best; <
> 28 vector<int> len(slen.begin(), slen.end());
> 29 memo.assign(lines.size()*(lines.size()+1)*len.size(), -1);
> 30 return rec(lines, 0, lines.size(), len, 0) + (lines.size()-1);
36 } | 31 }
37 best = INT_MAX; <
38 for(int v=lines[i]; v<=V; ++v) { <
39 best = min(best, dp[v]); <
40 dp_neo[v] = abs(v - lines[i]) + best; <
41 } | 32
42 dp.swap(dp_neo); <
> 33 vector<int> memo;
> 34 int rec(const vector<int>& lines, int s, int e,
> 35 const vector<int>& len, int cur_len) {
> 36 if(s+1 == e)
> 37 return abs(lines[s] - len[cur_len]);
43 } | 38
> 39 int key = (s*(lines.size()+1)+e)*len.size()+cur_len;
> 40 if(memo[key] != -1)
44 return dp[0] + N-1; | 41 return memo[key];
> 42
> 43 int result = 0x1fffffff;
> 44 for(int base_len=0; base_len<len.size(); ++base_len)
> 45 for(int m=s+1; m<e; ++m)
> 46 result = min(result,
> 47 rec(lines, s, m, len, base_len) +
> 48 rec(lines, m, e, len, base_len) + abs(le
> 49 return memo[key] = result;
45 } 50 }
46 }; 51 };
47 52
48 // BEGIN CUT HERE 53 // BEGIN CUT HERE
49 #include <ctime> 54 #include <ctime>
50 double start_time; string timer() 55 double start_time; string timer()
51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000)
................................................................................................................................................................................
79 END 84 END
80 CASE(3) 85 CASE(3)
81 int lines_[] = { 250, 105, 155, 205, 350 } 86 int lines_[] = { 250, 105, 155, 205, 350 }
82 ; 87 ;
83 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
84 int _ = 499; 89 int _ = 499;
85 END 90 END
> 91 /*
86 CASE(4) 92 CASE(4)
87 int lines_[] = {0}; | 93 int lines_[] = ;
88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 94 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
89 int _ = 0; | 95 int _ = ;
90 END <
91 CASE(5) <
92 int lines_[] = {1}; <
93 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); <
94 int _ = 1; <
95 END 96 END
96 CASE(5) 97 CASE(5)
97 int lines_[] = {10}; | 98 int lines_[] = ;
98 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 99 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
99 int _ = 10; | 100 int _ = ;
100 END 101 END
101 CASE(5) <
102 int lines_[] = {10,10}; <
103 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); <
104 int _ = 11; <
105 END <
106 CASE(5) <
107 int lines_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000, <
108 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); <
109 int _ = 1000049; <
110 END <
111 <
> 102 */
112 } 103 }
113 // END CUT HERE 104 // END CUT HERE