TopCoder SRM596: ColorfulRoad
dp[現在の位置] = 最小ステップ数として動的計画法を適用する
public class ColorfulRoad { public int getMin(string road) { int n = road.Length; int inf = 1 << 30; var dp = Enumerable.Repeat(inf, n).ToArray(); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if ("RGBR".Contains(road[j].ToString() + road[i].ToString())) { dp[i] = Math.Min(dp[i], dp[j] + (i - j) * (i - j)); } } } if (dp.Last() == inf) return -1; return dp.Last(); } }