TopCoder SRM596 Div2 Level 2 ColorfulRoad

DPの問題。

dp[i]をi+1文字目までの最小値と定義する。あとは、今の文字と次の文字をそれぞれi,j番目として二重ループでdpの内容を更新していけばよい。

dp[j] = min(dp[j], dp[i]+(j-i)*(j-i)); // j > i

ただし、更新できる条件はRGBの順序である必要があるので

colorid(road[j]) == (colorid(road[i]) + 1) % 3

を満たす必要がある。R,G,Bをそれぞれ0,1,2で表すことでプログラムがすっきりする。