読者です 読者をやめる 読者になる 読者になる

SRM411 Div1Easy SentenceDecomposion

問題
任意の文字の位置を入れ替えた部分文字列の候補が複数与えられる。
重複を許してこれらを接続して、与えられた元の文を構成するものを考える。そのために部分文字列の文字位置の入れ替えが必要であるが、その回数の総和が最小であるものを答えよ。ただしそのようなものが存在しない場合は -1 を出力せよ。

解法

dp[元の文の文字位置] := 最小のスワップ回数

元の文の各文字位置に対して、部分文字列の候補を全てを当てはめてDPする。
部分的に文字列をソートしたとき一致するかを見ると良い。

class SentenceDecomposition {
public:
  int decompose( string sentence, vector <string> validWords ) {
    
    int const N  = validWords.size();
    int const SN = sentence.size();
    int dp[55]; memset(dp, -1, sizeof dp);
    
    dp[0] = 0;
    for(int i=0; i<SN; i++) {
      for(int k=0; k<N; k++) {
	const string& STR = validWords[k];
	string str(STR);
	int const M = STR.size();
	if(dp[i] < 0) continue;
	const string& PART = string(sentence.begin()+i, sentence.begin()+i+M);
	string part(PART);
	sort(ALL(part));
	sort(ALL(str));
	if(part == str) {
	  int cnt = 0;
	  for(int ii=0; ii<M; ii++) {
	    cnt += STR[ii] != PART[ii];
	  }
	  if(dp[i+M] < 0) {
	    dp[i+M] = dp[i]+cnt;
	  }
	  else {
	    dp[i+M] = min(dp[i+M], dp[i]+cnt);
	  }
	}
      }
    }
    
    return dp[SN];
  }
};