1、DP的算法~~~
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 #include <list> 9 #include <ctime> 10 #include <set> 11 #include <queue> 12 13 using namespace std; 14 typedef long long ll; 15 class TheLargestString { 16 public: 17 string find(string s, string t) { 18 string dp[100][2]; 19 string res; 20 int sz = s.size(); 21 dp[0][0] = s[0]; 22 dp[0][1] = t[0]; 23 24 for (int i = 1; i < sz; i++) { 25 string curs; 26 curs = curs + s[i]; 27 string curt; 28 curt = curt + t[i]; 29 30 for (int j = i; j > 0; j--) { 31 string tc = dp[j - 1][0] + curs + dp[j - 1][1] + curt; 32 string tc2 = (dp[j][0] + dp[j][1]); 33 if (tc > tc2) { 34 dp[j][0] = dp[j - 1][0] + curs; 35 dp[j][1] = dp[j - 1][1] + curt; 36 } 37 } 38 string t0 = curs + curt; 39 if (t0 > (dp[0][0] + dp[0][1])) { 40 dp[0][0] = curs; 41 dp[0][1] = curt; 42 } 43 } 44 for (int i = 0; i < sz; i++) { 45 string t = dp[i][0] + dp[i][1]; 46 if (t > res) 47 res = t; 48 } 49 return res; 50 } 51 };