UTPC2014 D - ラボライブ タフグローバルフェスティバル
解法
M=1,2 の場合は容易に解ける. 以降ではM=3とする.
まず下準備として押す場所で同じ場所が連続して来る場合は結合して一つの区間にしておこう.
とりあえず一番近い指を使う貪欲を考えてみると,
p1 <--> 指1 <-> p2 <--> 指2 <-> 指3 , s1=2, t1 = s2 = 3
みたいな場合では明らかに最適でない.(p2は指2で押さないと無理)
次にどの指を使うか,O(2N)の状態数があるのでDPでできそう.
最近押したのがpx[i],py[i]であるとすると,s[i]=t[i-1]であるため必ずpx[i-1],py[i-1]にも指が置かれていたことになる.
なので1つの指はpx[j],py[j]にあったとすると全ての状態を表せるため,
dp[i][j] := (指が i, i-1, jを押している状態にできるか) とおく.
もしdp[i][j]がtrueなら
if(i-1でi+1を押せる) dp[i+1][j] = true
if(jでi+1を押せる) dp[i+1][i-1] = true
と配って行くDPをすれば良い.
なお座標は指1,指2,指3,p1,p2,...,pNと繋げて持っておくと便利.
メモ
結構好きだけどM=3だけで良くない？
