SRM306 div2 difficult

貪欲法で解けそうだけど、

oldText:aaaa
newText:abacacaaaa
とかのときはだめになる．
//貪欲法:4  a[b]a[c]a[c]a[aaa]
 本当の答え:1  a[bacacacaa]aaa

典型的な動的計画法。

  int minDist(vector  oldText, vector  newText) {
    string oldT = ""; string newT = "";
    for(int i = 0, sz = oldText.size(); i < sz; i++) {
      oldT += oldText[i];
    }
    for(int i = 0, sz = newText.size(); i < sz; i++) {
      newT += newText[i];
    }
    int newLen = newT.length(); int oldLen = oldT.length();
    fill(dp[0], dp[0]+1001*1001, INF);

    //EQUAL TO  [int minDist(string oldT, string newT)]
    //trigger
    for(int i = 0; i < newLen; i++) {
      if(oldT[0] == newT[i]) {
	dp[0][i] = 1;
      }
    }
    if(dp[0][0] == 1) dp[0][0] = 0;

//Dynamic Programming START!!
    for(int i = 1; i < oldLen; i++) {
 //j++にすると、何回も書き換えられる可能性がある．
      for(int j = newLen-1; j >= i; j--) {

	if(oldT[i] == newT[j]) {
	  for(int k = j-1; k >= 0; k--) {
	    int isAdjacent = (k == j-1) ? 0 : 1;
	    if(dp[i-1][k] != INF) {
	      dp[i][j] = min(dp[i][j], dp[i-1][k]+isAdjacent);
	    }
	  }
	} //if end
      }
    } //for i

    for(int i = 0; i < newLen-1; i++) {
      if(dp[oldLen-1][i] != INF) {
	dp[oldLen-1][i]++;
      }
    }
    int ans = *min_element(dp[oldLen-1], dp[oldLen-1]+newLen);
    return ans == INF ? -1 : ans;
  }

二重ループにするとこんな感じになるのかな．

  int minDist(vector <string> oldText, vector <string> newText) {
    string oldT = ""; string newT = "";
    for(int i = 0, sz = oldText.size(); i < sz; i++) {
      oldT += oldText[i];
    }
    for(int i = 0, sz = newText.size(); i < sz; i++) {
      newT += newText[i];
    }
    int newLen = newT.length(); int oldLen = oldT.length();
    fill(dp[0], dp[0]+1001*1001, INF);

    //minDist(string oldT, string newT)
    //trigger
    for(int i = 0; i < newLen; i++) {
      dp[0][i] = 1;
    }
    if(dp[0][0] == 1) dp[0][0] = 0;


    for(int i = 0; i < oldLen; i++) {
      int mini = INF;
      for(int j = i; j < newLen; j++) {
	if(oldT[i] == newT[j]) {
	  dp[i+1][j+1] = dp[i][j];
	  mini = min(dp[i+1][j+1], mini);
	} else {
	  if(mini != INF) {
	    dp[i+1][j+1] = mini+1;
	  }
	} // end if
      }
    }
    return dp[oldLen][newLen] == INF ? -1 : dp[oldLen][newLen];
  }