ABC052 D - Walk and Teleport
解法
この手の問題は、まずテレポートをする回数を固定しましょう。
ということで、テレポートする回数を回とします。このとき、徒歩で移動する区間の個数は個になります。
徒歩で移動する区間はどこになるかというと、区間の距離が小さい方から選んだ個になります。
前から順番に、徒歩でいくと決めた区間なら徒歩で1つ先の場所へ、徒歩でいかないと決めた区間は1つ先の場所へテレポートで移動すればよいです。
ということで、これを繰り返していると、結局は
ならば徒歩で、そうでなければテレポートで移動すればよいことになります。
ということで、全ての区間について、距離にをかけたものと、を比較して、小さいものを足していけば答えとなります。