EllysPearls [2019 Topcoder Open Algo 1B Hard]

N個の真珠がある。
i番目の真珠の色はpearls[i]であり、1～Mである。
ある真珠を抜き出して、ある箇所に差し込むという操作を行う。
同色の真珠は連続して並んでいる状態にしたい。
操作の最小回数は？

1≦N≦50
1≦M≦15

解説

問題を少し読み替える。
今回の問題では差し込む場所は好きに選べるので、抜き出すべき要素を全部抜き出してから、
適切に入れても特に結果は変わらない。
よって、操作を「ある真珠を抜き出す」という操作だけにして考える。
つまり、ある真珠を適切に抜き出して、同色の真珠を連続して並ぶ状態にする最小回数を求める。
　
DPをしよう。
dp[i][msk] := i番目の真珠まで操作が終わっていて、残っている真珠の色の集合がmskのときの操作の最小回数
これで次の色nxtと場所toを全探索する遷移を行う。
かかるコストは次の色nxtと違う色の個数である。
これは累積和で区間に含まれるある色の個数の総和を取れるようにすれば大丈夫。
O(N*2^M*M*N)で計算量が少し心配なので、ちょっとだけ枝刈りをしておく。
遷移先の場所toは、次の色nxtの色になっている所だけを使うことにする。
これにより、どれくらい枝刈りできているかわからないが、テストしたらだいぶ早くなったので、出すとAC

struct EllysPearls {
	int dp[51][1 << 15];
	int sm[15][51];
	vector<int> go[15];
	int getMin(int N, int M, vector <int> A) {
		rep(i, 0, N) A[i]--;
		rep(i, 0, N) go[A[i]].push_back(i + 1);
		rep(i, 0, M) rep(j, 0, N + 1) sm[i][j] = 0;
		rep(i, 0, N) sm[A[i]][i + 1] = 1;
		rep(m, 0, M) rep(i, 1, N + 1) sm[m][i] += sm[m][i - 1];

		rep(i, 0, N + 1) rep(msk, 0, 1 << M) dp[i][msk] = inf;
		dp[0][0] = 0;
		rep(i, 0, N + 1) rep(msk, 0, 1 << M) if (dp[i][msk] < inf) {
			rep(nxt, 0, M) if (!(msk & (1 << nxt))) {
				fore(to, go[nxt]) if (i < to) {
					chmin(dp[to][msk | (1 << nxt)], dp[i][msk] + (to - i) - (sm[nxt][to] - sm[nxt][i]));
				}
			}
		}

		int ans = inf;
		rep(i, 1, N + 1) rep(msk, 0, 1 << M) chmin(ans, dp[i][msk] + N - i);
		return ans;
	}
};