ABC197 E-Traveler

タイトルが髭男のアルバムっぽい

解説AC

どの色についても、左端のボールと右端のボールは必ず取らないといけなく、それらを取らないと次の色は取れない

よって間のボールは関係ないことがわかる

そのままだとめんどいので色について座標圧縮する(座標圧縮しても変わらない)

色nのボールの取り方は色n+1のときにしか影響しない

よって色nで最後に右と左どちらにいたかを状態として記録してDP

遷移

code:dp.cpp

//Ai0は色iの左端の座標,Ai1は右端の座標

ll z = Aij;

ll m = abs(z - Ai+11) + abs(Ai+11 - Ai+10);

ll l = abs(z - Ai+10) + abs(Ai+11 - Ai+10);

dpi + 10 = min(dpij + m, dpi + 10);

dpi + 11 = min(dpij + l, dpi + 11);

感想

面白かった

2次元vectorは便利

添字は面倒(0-indexed?1-indexed?)

配列外参照をやめよう