色毎に分けて考える. 回収したボールを並べると,色が広義単調増加なので, 同じ色がひと塊となるから.
色 \(i \in N\) を固定して,色 \(i\) の座標だけを考える. 最適手順として,左端または右端で終える物が存在する. よって,左端か右端か \(in 2\) を持ちながら \(DP\) で全探索.
DP
色 \(i \in N\) を決めるとき,色 \(i-1\) が左端か右端かが決まっていれば, それまでのボールの選び順は無関係に定まる.
実装
最後に座標 \(0\) に戻ってくるので, 色 \(N\) の座標を \(0\) としておく.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll x(n), c(n);
rep(i,n){
cin >> x[i]>> c[i];
c[i]--;
px[c[i]].push_back(x[i]);
}
px[n].push_back(0);
rep(i,n+1){
sort(all(px[i]));
}
ll l = 0, r = 0;
dp[0] = 0;
dp[1] = 0;
rep(i,n+1){
if(px[i].size() == 0) continue;
swap(dp, old);
ll nl = px[i].front();
ll nr = px[i].back();
chmin(dp[1], old[0] + abs(l-nl) + abs(nl-nr));
chmin(dp[0], old[0] + abs(l-nr) + abs(nl-nr));
chmin(dp[1], old[1] + abs(r-nl) + abs(nl-nr));
chmin(dp[0], old[1] + abs(r-nr) + abs(nl-nr));
swap(l, nl);
swap(r, nr);
}
assert(dp[0] == dp[1]);
cout << min(dp[0], dp[1]) << endl;
return 0;
}