SRM321 div2

問題文の読み間違い。k-double stringsの個数を求める．0-strings ~ k-stringsまでの個数を求めるのではない．
問いの文はi-double stringsはk-double strings(i <= k)でもあるんだよ、といっているだけ．
easy

  int howMuch(vector <string> str, int k) {
    string s;
    for(int i = 0, len = str.size(); i < len ;i++) {
      s += str[i];
    }
    int len = s.length();
    int ans = 0;
    for(int i = 2; i <= len; i += 2) {
      for(int pos = 0; pos <= len-i; pos++) {
	string first = s.substr(pos, i/2);
	string second = s.substr(pos+i/2, i/2);
	int cnt = 0;
	for(int j = 0; j <= i/2; j++) {
	  if(first[j] != second[j]) {
	    cnt++;
	  }
	}
	if(cnt <= k) ans++;
      }
    }
    return ans;
  }

medium

//easyよりも簡単
#define INF (1<<30)
class Chocolate {
	public:
	int minSplitNumber(int width, int height, int nTiles) {
    int ans = INF;
    if(width < height) swap(width, height);
    for(int i = 1; i*i<= nTiles; i++) {
      int tmp = 2;
      if(nTiles%i == 0) {
        int a = i; //small
        int b = nTiles/i; //large
        if(height < a || width < b) continue;
        if(height == a || height == b) tmp--;
        if(width == b || width == a) tmp--;
        
        ans = min(ans, tmp);
      }
    }
    return (ans == INF) ? -1 : ans;       
	}
	

difficult
純粋なDPではおそらくとけない。とけるが、通った道も記憶していなければならないので、dp[len+1][len][len]みたいになる。
これでは、あまりメモ化する意味はない。（メモ化は、何回も値を参照するときに有効であることを意識する）
たとえば、dp[len+1][len](dp[cnt][length])とおくとする。
なぜなら、i個目の文字がprint_outされたとして、i+1個目の文字に行くとき、次に訪問していない文字が特定できないから。
たとえば、２個目に3番目の数に到達したとする。次に進みたいとき、一度出力した文字の場所をたどってしまう。

aaaa
0000
0123
???? <--DPにするならここをどう漸化式で表現するかだが、
???? <--通ったか通っていないか分からないので、表現できない。

この問題は再帰関数で表現すればいい。

aaabbaababb
TTTFTTTFTFF:通ったか
    .      ;現在位置（現在７文字出力完了)
   *   *   :次に行き当たる文字。右or左に最初に突き当たる条件をみたす文字。
//次に行き当たる文字を総当たり式に調べていくのはNG.
次の文字のときおそらく間に合わなくなる。
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaとか。

#define INF (1<<30)
class LexStringWriter {
  private:
    string str;
    string sorted;
    int go(int cnt, int pos);
    bool used[51];
	public:
	int minMoves(string s) {
    str = s;
    sorted = s;
    sort(sorted.begin(), sorted.end());
    memset(used, false, sizeof used);
    return go(0, 0)+s.length();
  }
};

//ここはもうちょっと簡略化できるかも。
int LexStringWriter::go(int cnt, int pos) {
  if(cnt == str.length() ) return 0;
  int ans;
  if(str[pos] == sorted[cnt] && used[pos] == false ) {
    used[pos] = true;
    ans = min(ans, go(cnt+1, pos) );
    used[pos] = false;
  } else {
    for(int i = pos+1; i < str.length(); i++) {
      if(str[i] == sorted[cnt] && used[i] == false ) {
        used[i] = true;
        ans = min(ans, go(cnt+1, i)+i-pos );
        used[i] = false;
      }
    }
    for(int i = pos-1; i >= 0; i--) {
      if(str[i] == sorted[cnt] && used[i] == false) {
        used[i] = true;
        ans = min(ans, go(cnt+1, i)+pos-i );
        used[i] = false;
      }
    }
  }
  return ans;
}