TCO2013 Round2A

難しすぎる。

300
解法：Greedyとか怖すぎなのでDPした。

import java.util.*;
public class TheLargestString{
	public String find(String a,String b){
		int n=a.length();
		String[][]dp=new String[n+1][n+1];
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)dp[i][j]="";
		dp[0][0]="";
		for(int i=0;i<n;i++){
			for(int j=0;j<=i;j++){
				if(dp[i][j].compareTo(dp[i+1][j])>0)dp[i+1][j]=dp[i][j];
				String s=dp[i][j].substring(0,j)+a.charAt(i)+dp[i][j].substring(j)+b.charAt(i);
				if(s.compareTo(dp[i+1][j+1])>0)dp[i+1][j+1]=s;
			}
		}
		String ret="";
		for(int i=0;i<=n;i++)if(ret.compareTo(dp[n][i])<0)ret=dp[n][i];
		return ret;
	}
}

他：知らない
Systest:通った(167th)
Rating
2018 -> 2081 (-37)
上がり幅が最近どんどん小さくなっている…