2013 TCO Round 2A Easy - TheLargestString (××)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12494&rd=15594
・文字列sと、文字列tが与えられる。
・sとtは同じ長さ。
・好きな位置を選択し、そこから構成されるsとtのサブ文字列を作り、sとtを結合する。
・このとき、最も辞書順に大きくなるような結合後の文字列を求める。
解き方
・一見、貪欲法で解けそう
・まずはsの大きくなる選び方で試してみる
・最後のサンプルがエラー。sの選び方に加え、選ばずにs+tの方が辞書順に大きくなる可能性が
あるため貪欲法では解けない。
・よってｄｐで解く必要がある。
・最初からｄｐを適用していくと、選び方を全探索しないといけないが、
後ろから適用していけば、現在の文字列をつなげるかどうかを判断すればよいので
計算量も間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheLargestString {
public: string find(string s, string t) {
int n=s.size();
pair<string,string> dp[60][60];
FORE(i,0,60)FORE(j,0,60)dp[i][j]=make_pair("","");
string ret="";
for(int i=n-1;i>=0;i--){
FORE(len,0,59){
if(dp[i][len]<dp[i+1][len])dp[i][len]=dp[i+1][len];
pair<string,string> tmp=make_pair(s[i]+dp[i+1][len-1].first,t[i]+dp[i+1][len-1].second);
if(len-1>=0 && tmp>dp[i][len])dp[i][len]=tmp;
ret=max(ret,dp[i][len].first+dp[i][len].second);
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheLargestString {
public: string find(string s, string t) {
int n=s.size();
pair<string,string> dp[60][60];
FORE(i,0,60)FORE(j,0,60)dp[i][j]=make_pair("","");
string ret="";
for(int i=n-1;i>=0;i--){
FORE(len,0,59){
if(dp[i][len]<dp[i+1][len])dp[i][len]=dp[i+1][len];
pair<string,string> tmp=make_pair(s[i]+dp[i+1][len-1].first,t[i]+dp[i+1][len-1].second);
if(len-1>=0 && tmp>dp[i][len])dp[i][len]=tmp;
ret=max(ret,dp[i][len].first+dp[i][len].second);
}
}
return ret;
}
};
