c009363094 2013-04-06 kinaba: #include <iostream> c009363094 2013-04-06 kinaba: #include <sstream> c009363094 2013-04-06 kinaba: #include <iomanip> c009363094 2013-04-06 kinaba: #include <vector> c009363094 2013-04-06 kinaba: #include <string> c009363094 2013-04-06 kinaba: #include <map> c009363094 2013-04-06 kinaba: #include <set> c009363094 2013-04-06 kinaba: #include <algorithm> c009363094 2013-04-06 kinaba: #include <numeric> c009363094 2013-04-06 kinaba: #include <iterator> c009363094 2013-04-06 kinaba: #include <functional> c009363094 2013-04-06 kinaba: #include <complex> c009363094 2013-04-06 kinaba: #include <queue> c009363094 2013-04-06 kinaba: #include <stack> c009363094 2013-04-06 kinaba: #include <cmath> c009363094 2013-04-06 kinaba: #include <cassert> c009363094 2013-04-06 kinaba: using namespace std; c009363094 2013-04-06 kinaba: typedef long long LL; c009363094 2013-04-06 kinaba: typedef long double LD; c009363094 2013-04-06 kinaba: typedef complex<LD> CMP; c009363094 2013-04-06 kinaba: c009363094 2013-04-06 kinaba: template<typename T> c009363094 2013-04-06 kinaba: struct DP2 c009363094 2013-04-06 kinaba: { c009363094 2013-04-06 kinaba: const int N1, N2; c009363094 2013-04-06 kinaba: vector<T> data; c009363094 2013-04-06 kinaba: DP2(int N1, int N2, const T& t = T()) c009363094 2013-04-06 kinaba: : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); } c009363094 2013-04-06 kinaba: T& operator()(int i1, int i2) c009363094 2013-04-06 kinaba: { return data[ (i1*N2)+i2 ]; } c009363094 2013-04-06 kinaba: void swap(DP2& rhs) c009363094 2013-04-06 kinaba: { data.swap(rhs.data); } c009363094 2013-04-06 kinaba: }; c009363094 2013-04-06 kinaba: c009363094 2013-04-06 kinaba: class TheLargestString { public: c009363094 2013-04-06 kinaba: string find(string s, string t) c009363094 2013-04-06 kinaba: { c009363094 2013-04-06 kinaba: const int N = s.size(); c009363094 2013-04-06 kinaba: DP2< pair<string,string> > best(N+1,N+1); c009363094 2013-04-06 kinaba: for(int i=N-1; i>=0; --i) c009363094 2013-04-06 kinaba: { c009363094 2013-04-06 kinaba: for(int len=1; len<=N-i; ++len) c009363094 2013-04-06 kinaba: { c009363094 2013-04-06 kinaba: pair<string, string> cand = best(i+1, len); c009363094 2013-04-06 kinaba: pair<string, string> cand2(s[i]+best(i+1, len-1).first, t[i]+best(i+1,len-1).second); c009363094 2013-04-06 kinaba: if(cand.first+cand.second < cand2.first+cand2.second) c009363094 2013-04-06 kinaba: cand = cand2; c009363094 2013-04-06 kinaba: best(i, len) = cand; c009363094 2013-04-06 kinaba: } c009363094 2013-04-06 kinaba: } c009363094 2013-04-06 kinaba: string ans; c009363094 2013-04-06 kinaba: for(int len=0; len<=N; ++len) c009363094 2013-04-06 kinaba: ans = max(ans, best(0,len).first + best(0,len).second); c009363094 2013-04-06 kinaba: return ans; c009363094 2013-04-06 kinaba: } c009363094 2013-04-06 kinaba: }; c009363094 2013-04-06 kinaba: c009363094 2013-04-06 kinaba: // BEGIN CUT HERE c009363094 2013-04-06 kinaba: #include <ctime> c009363094 2013-04-06 kinaba: double start_time; string timer() c009363094 2013-04-06 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } c009363094 2013-04-06 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) c009363094 2013-04-06 kinaba: { os << "{ "; c009363094 2013-04-06 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) c009363094 2013-04-06 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } c009363094 2013-04-06 kinaba: void verify_case(const string& Expected, const string& Received) { c009363094 2013-04-06 kinaba: bool ok = (Expected == Received); c009363094 2013-04-06 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; c009363094 2013-04-06 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } c009363094 2013-04-06 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); c009363094 2013-04-06 kinaba: #define END verify_case(_, TheLargestString().find(s, t));} c009363094 2013-04-06 kinaba: int main(){ c009363094 2013-04-06 kinaba: CASE(0) c009363094 2013-04-06 kinaba: string s = "ab"; c009363094 2013-04-06 kinaba: string t = "zy"; c009363094 2013-04-06 kinaba: string _ = "by"; c009363094 2013-04-06 kinaba: END c009363094 2013-04-06 kinaba: CASE(1) c009363094 2013-04-06 kinaba: string s = "abacaba"; c009363094 2013-04-06 kinaba: string t = "zzzaaaa"; c009363094 2013-04-06 kinaba: string _ = "cbaaaa"; c009363094 2013-04-06 kinaba: END c009363094 2013-04-06 kinaba: CASE(2) c009363094 2013-04-06 kinaba: string s = "x"; c009363094 2013-04-06 kinaba: string t = "x"; c009363094 2013-04-06 kinaba: string _ = "xx"; c009363094 2013-04-06 kinaba: END c009363094 2013-04-06 kinaba: CASE(3) c009363094 2013-04-06 kinaba: string s = "abbabbabbababaaaabbababab"; c009363094 2013-04-06 kinaba: string t = "bababbaabbbababbbbababaab"; c009363094 2013-04-06 kinaba: string _ = "bbbbbbbbbbbbbbbbbbaaab"; c009363094 2013-04-06 kinaba: END c009363094 2013-04-06 kinaba: /* c009363094 2013-04-06 kinaba: CASE(4) c009363094 2013-04-06 kinaba: string s = ; c009363094 2013-04-06 kinaba: string t = ; c009363094 2013-04-06 kinaba: string _ = ; c009363094 2013-04-06 kinaba: END c009363094 2013-04-06 kinaba: CASE(5) c009363094 2013-04-06 kinaba: string s = ; c009363094 2013-04-06 kinaba: string t = ; c009363094 2013-04-06 kinaba: string _ = ; c009363094 2013-04-06 kinaba: END c009363094 2013-04-06 kinaba: */ c009363094 2013-04-06 kinaba: } c009363094 2013-04-06 kinaba: // END CUT HERE