109f2a9050 2012-09-08 kinaba: #include <iostream> 109f2a9050 2012-09-08 kinaba: #include <sstream> 109f2a9050 2012-09-08 kinaba: #include <iomanip> 109f2a9050 2012-09-08 kinaba: #include <vector> 109f2a9050 2012-09-08 kinaba: #include <string> 109f2a9050 2012-09-08 kinaba: #include <map> 109f2a9050 2012-09-08 kinaba: #include <set> 109f2a9050 2012-09-08 kinaba: #include <algorithm> 109f2a9050 2012-09-08 kinaba: #include <numeric> 109f2a9050 2012-09-08 kinaba: #include <iterator> 109f2a9050 2012-09-08 kinaba: #include <functional> 109f2a9050 2012-09-08 kinaba: #include <complex> 109f2a9050 2012-09-08 kinaba: #include <queue> 109f2a9050 2012-09-08 kinaba: #include <stack> 109f2a9050 2012-09-08 kinaba: #include <cmath> 109f2a9050 2012-09-08 kinaba: #include <cassert> 109f2a9050 2012-09-08 kinaba: using namespace std; 109f2a9050 2012-09-08 kinaba: typedef long long LL; 109f2a9050 2012-09-08 kinaba: typedef long double LD; 109f2a9050 2012-09-08 kinaba: typedef complex<LD> CMP; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: class WhiteSpaceEditing { public: 109f2a9050 2012-09-08 kinaba: int getMinimum(vector <int> lines) 109f2a9050 2012-09-08 kinaba: { 109f2a9050 2012-09-08 kinaba: set<int> slen(lines.begin(), lines.end()); 109f2a9050 2012-09-08 kinaba: slen.insert(0); 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: vector<int> len(slen.begin(), slen.end()); 109f2a9050 2012-09-08 kinaba: memo.assign(lines.size()*(lines.size()+1)*len.size(), -1); 109f2a9050 2012-09-08 kinaba: return rec(lines, 0, lines.size(), len, 0) + (lines.size()-1); 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: vector<int> memo; 109f2a9050 2012-09-08 kinaba: int rec(const vector<int>& lines, int s, int e, 109f2a9050 2012-09-08 kinaba: const vector<int>& len, int cur_len) { 109f2a9050 2012-09-08 kinaba: if(s+1 == e) 109f2a9050 2012-09-08 kinaba: return abs(lines[s] - len[cur_len]); 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: int key = (s*(lines.size()+1)+e)*len.size()+cur_len; 109f2a9050 2012-09-08 kinaba: if(memo[key] != -1) 109f2a9050 2012-09-08 kinaba: return memo[key]; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: int result = 0x1fffffff; 109f2a9050 2012-09-08 kinaba: for(int base_len=0; base_len<len.size(); ++base_len) 109f2a9050 2012-09-08 kinaba: for(int m=s+1; m<e; ++m) 109f2a9050 2012-09-08 kinaba: result = min(result, 109f2a9050 2012-09-08 kinaba: rec(lines, s, m, len, base_len) + 109f2a9050 2012-09-08 kinaba: rec(lines, m, e, len, base_len) + abs(len[cur_len] - len[base_len])); 109f2a9050 2012-09-08 kinaba: return memo[key] = result; 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: }; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: // BEGIN CUT HERE 109f2a9050 2012-09-08 kinaba: #include <ctime> 109f2a9050 2012-09-08 kinaba: double start_time; string timer() 109f2a9050 2012-09-08 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 109f2a9050 2012-09-08 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 109f2a9050 2012-09-08 kinaba: { os << "{ "; 109f2a9050 2012-09-08 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 109f2a9050 2012-09-08 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 109f2a9050 2012-09-08 kinaba: void verify_case(const int& Expected, const int& Received) { 109f2a9050 2012-09-08 kinaba: bool ok = (Expected == Received); 109f2a9050 2012-09-08 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 109f2a9050 2012-09-08 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 109f2a9050 2012-09-08 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 109f2a9050 2012-09-08 kinaba: #define END verify_case(_, WhiteSpaceEditing().getMinimum(lines));} 109f2a9050 2012-09-08 kinaba: int main(){ 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: CASE(0) 109f2a9050 2012-09-08 kinaba: int lines_[] = { 3, 2, 3 }; 109f2a9050 2012-09-08 kinaba: vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109f2a9050 2012-09-08 kinaba: int _ = 6; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(1) 109f2a9050 2012-09-08 kinaba: int lines_[] = { 0 }; 109f2a9050 2012-09-08 kinaba: vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109f2a9050 2012-09-08 kinaba: int _ = 0; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(2) 109f2a9050 2012-09-08 kinaba: int lines_[] = { 1, 2, 4 } 109f2a9050 2012-09-08 kinaba: ; 109f2a9050 2012-09-08 kinaba: vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109f2a9050 2012-09-08 kinaba: int _ = 6; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(3) 109f2a9050 2012-09-08 kinaba: int lines_[] = { 250, 105, 155, 205, 350 } 109f2a9050 2012-09-08 kinaba: ; 109f2a9050 2012-09-08 kinaba: vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109f2a9050 2012-09-08 kinaba: int _ = 499; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: /* 109f2a9050 2012-09-08 kinaba: CASE(4) 109f2a9050 2012-09-08 kinaba: int lines_[] = ; 109f2a9050 2012-09-08 kinaba: vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109f2a9050 2012-09-08 kinaba: int _ = ; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(5) 109f2a9050 2012-09-08 kinaba: int lines_[] = ; 109f2a9050 2012-09-08 kinaba: vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); 109f2a9050 2012-09-08 kinaba: int _ = ; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: */ 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: // END CUT HERE