JOI2009春合宿Day4 塗り箸(Chopsticks)

割り箸かと思ってました。

問題

http://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day4_23.pdf

解法

区間DPをします。
ある区間に色を塗るとき、その区間の両端の目的の色と塗る色が違うと無駄にはみ出して塗っていることになるので、両端の目的の色が塗った色と同じと考えてよいです。
だから区間をどの色で塗ったかの情報は必要ありません。
そこでとします。
塗る区間同士が中途半端に重なるのは何も得しないので、「重ねないように塗る/区間同士が内包の関係にあるように重ねて塗る」だけで必ず最小手数が達成できます。
内包するように塗るのは、同じ色の離れた区間を先に一度に塗ってしまうことで1手間で塗れちゃう、みたいなのです。
そこで、DPで2つの区間を併合するときに併合後の両端が同じ色なら1手間減らす処理を入れます。
すると漸化式はこうなります。

ちなみに普通にfor文回すと順番がやばそうです。(狭い順からやるのが一番よい？)

実装

狭い順が個人的に気持ち悪かったのでメモ化再帰書きました。

using namespace std;

#define int long long

const int INF = LLONG_MAX/2;

int N;
string S;
int memo[300][300];

int DFS(int l, int r)
{
	if (memo[l][r] != INF) return memo[l][r];
	for (int i = l; i < r; i++)
	{
		memo[l][r] = min(memo[l][r], DFS(l, i) + DFS(i + 1, r) - (S[l] == S[r]));
	}
	return memo[l][r];
}

signed main()
{
	fill((int*)memo, (int*)memo + 300*300, INF);
	cin >> N >> S;
	for (int i = 0; i < N; i++)
	{
		memo[i][i] = 1;
	}
	printf("%lld\n", DFS(0, N - 1));
	cin >> N;
	return 0;
}