https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d
解説
https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144334
ここから競技プログラミングになれていないと、満点解答を狙うには難しいかもしれない。
さて、なれている諸君は動的計画法がぽっとでてくるだろう。
自分は「最小値を求める」という所から動的計画法かもと思ってちょっと考えるとそうだったパターンである。
DPは、
dp[i][lst] := i列目まで塗り替えが完了していて、最後の色がlstである組み合わせ
で作る。
dp[i][lst] -> dp[i + 1][lst]の遷移以外を行う。
最初はどの色でもいいので、R,B,W,#を0,1,2,3として、何でも良い4を初期値としておこう。
dp[0][4] = 0, dp[他][他]=∞
int N; string S[5]; int dp[1010][5]; map<char, int> dic = { {'R', 0}, {'B', 1}, {'W', 2}, {'#', 3} }; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, 5) cin >> S[i]; rep(i, 0, N + 1) rep(lst, 0, 5) dp[i][lst] = inf; dp[0][4] = 0; rep(i, 0, N) rep(lst, 0, 5) if (dp[i][lst] < inf) { rep(nxt, 0, 3) if (lst != nxt) { int cst = 0; rep(j, 0, 5) if (dic[S[j][i]] != nxt) cst++; chmin(dp[i + 1][nxt], dp[i][lst] + cst); } } int ans = inf; rep(lst, 0, 3) chmin(ans, dp[N][lst]); cout << ans << endl; }