Diff
Not logged in

Differences From Artifact [13e543b5a0b1db44]:

To Artifact [124c7549ad607d0d]:


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