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 10 #include <iterator>
11 11 #include <functional>
12 12 #include <complex>
13 13 #include <queue>
14 14 #include <stack>
15 15 #include <cmath>
16 16 #include <cassert>
17 -#include <cstring>
18 17 using namespace std;
19 18 typedef long long LL;
20 -typedef complex<double> CMP;
19 +typedef long double LD;
20 +typedef complex<LD> CMP;
21 21
22 22 class WhiteSpaceEditing { public:
23 23 int getMinimum(vector <int> lines)
24 24 {
25 - const int N = lines.size();
26 - const int V = *max_element(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)
31 - {
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;
36 - }
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 - }
42 - dp.swap(dp_neo);
43 - }
44 - return dp[0] + N-1;
25 + set<int> slen(lines.begin(), lines.end());
26 + slen.insert(0);
27 +
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);
31 + }
32 +
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]);
38 +
39 + int key = (s*(lines.size()+1)+e)*len.size()+cur_len;
40 + if(memo[key] != -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(len[cur_len] - len[base_len]));
49 + return memo[key] = result;
45 50 }
46 51 };
47 52
48 53 // BEGIN CUT HERE
49 54 #include <ctime>
50 55 double start_time; string timer()
51 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
................................................................................
79 84 END
80 85 CASE(3)
81 86 int lines_[] = { 250, 105, 155, 205, 350 }
82 87 ;
83 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
84 89 int _ = 499;
85 90 END
91 +/*
86 92 CASE(4)
87 -int lines_[] = {0};
93 + int lines_[] = ;
88 94 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
89 - int _ = 0;
90 -END
91 -CASE(5)
92 -int lines_[] = {1};
93 - vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
94 - int _ = 1;
95 + int _ = ;
95 96 END
96 97 CASE(5)
97 - int lines_[] = {10};
98 + int lines_[] = ;
98 99 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_));
99 - int _ = 10;
100 + int _ = ;
100 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,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,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 104 // END CUT HERE