SRM 526.5 Div2 Hard MagicNaming

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11674&rd=14762
文字列がn個存在し、これらを辞書式最小になるように結合したものがSとなる。このnを最大化せよ。

やりかた

DP。
dp[j][i] := （文字列Sのj文字目まででS[i...j]を1つの文字列として使用するときの最大の分割数n）でdp。

分割した文字列a[0]、a[1]、a[2]、a[3]...をこの順に結合した時に辞書式最小になる
⇔ すべてのiに対して a[i]a[i + 1] <= a[i + 1]a[i]

すると

S[k...i]S[i...j] <= S[i...j]S[k...i] となる k < i < j という組み合わせに対して
dp[j][i] = max(dp[i][k] + 1)

となる。

以下ソース。

class MagicNaming {
public:
  int maxReindeers(string magicName) {
    int L = magicName.length();
    vector<vector<int> > dp(L + 1, vector<int>(L + 1, -INF));
    for(int i = 1; i <= L; i++) dp[i][0] = 1;
    for(int i = 0; i < L; i++)
      for(int j = i + 1; j <= L; j++)
	for(int k = 0; k < i; k++){
	  string A = magicName.substr(k, i - k);
	  string B = magicName.substr(i, j - i);
	  if(A + B <= B + A)
	    dp[j][i] = max(dp[j][i], dp[i][k] + 1);
	}

    int ans = 0;
    for(int i = 0; i <= L; i++) ans = max(ans, dp[L][i]);
 
    return ans;
  }
};