問題一覧 > 通常問題

No.2573 moving up

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : aplysiaSheep / テスター : deuteridayo 👑 AngrySadEight Magentor ragna
1 ProblemId : 10401 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-02 08:19:49

問題文

以下の図のような盤面があります。
縦は HH 行であり、ii 行目には i+W−1i + W - 1 個のマスが存在し、ii 行目の左から jj 個目のマスの座標は (i,j)(i, j) です。
それぞれのマスは周囲の 66 方向のマスと隣接しています。
より厳密には、(i,j)(i, j) のマスは (i−1,j−1)(i-1, j-1), (i−1,j)(i-1, j), (i,j−1)(i, j-1), (i,j+1)(i, j+1), (i+1,j)(i+1, j), (i+1,j+1)(i+1, j+1) の各マスに、マスが存在する限り隣接しています。
この盤上に、WW 個のコマが置かれています。コマ kk ははじめ(xk,yk)(x_k, y_k)に置かれています。

あなたは以下の操作を何度でも行うことができます。

  • コマを一つ選び、隣接するマスにコスト 11 を払って移動させる。(同じマスに複数のコマが存在してもかまいません。また、盤面の外に移動することはできません。)

    • 全てのコマが 11 行目の WW 個のマスに一つずつ置かれている状態にするのに必要な、最小のコストを求めてください。

    制約

    • 1≤H,W≤2001≤H, W≤200
    • 1≤xi≤H1≤x_i≤H
    • 1≤yi≤W+xi−11≤y_i≤W + x_i - 1
    • (xi,yi)(x_i, y_i)は互いに異なる
    • 入力される値は全て整数

    入力

    H WH\ W
x1 y1x_1\ y_1
x2 y2x_2\ y_2
⋮\vdots        
xW yWx_W\ y_W

    出力

    最小のコストを出力せよ。

    サンプル

    サンプル1
    入力
    3 2
3 4
3 1
    出力
    4

    図のように移動するのが最善であり、必要な最小コストは4です。
    サンプル2
    入力
    3 2
2 1
3 1
    出力
    4

    図のように移動するのが最善です。最上段のマスに一つずつ配置しなければならない点に注意してください。
    サンプル3
    入力
    4 10
1 4
1 7
1 10
3 2
3 4
3 5
3 7
4 2
4 7
4 8
    出力
    19

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。