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