ビットDP 練習問題 5 D(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
N 個の宝石があります。i 個目の宝石は座標 (x_i,y_i) にあります。
あなたは 1 回の移動で (x,y) から (x+1,y),(x-1,y),(x,y+1),(x,y-1) に移動できます。
いまあなたは (0,0) にいます。
各宝石が置かれた座標に訪れることで、その宝石を獲得できます。
すべての宝石を獲得して座標 (0,0) に戻ってくるとき、必要な移動回数の最小値を求めてください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
x_1 y_1
x_2 y_2
...
x_N y_N
・1 行目には、宝石の数を表す整数 N が与えられます。
・続く N 行には、宝石の座標 (x_i, y_i) が空白区切りで与えられます。
・入力は合計で 1 + N 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
すべての宝石を獲得して座標 (0,0) に戻ってくるとき、必要な移動回数の最小値を求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 17
・-10^9 ≦ x_i, y_i ≦ 10^9
・(x_i, y_i) ≠ (0, 0)
・(x_i, y_i) ≠ (x_j, y_j) (i ≠ j)
- 入力例1
-
3
2 3
1 4
3 0
- 出力例1
-
14
- 入力例2
-
5
-2 2
3 -2
3 -1
0 3
4 0
- 出力例2
-
22
- 入力例3
-
16
780812969 -389561801
-913111680 72066219
-522401144 26548740
109962055 63358792
-738621667 -218469084
587242929 872432947
-8794464 934626682
-349169743 -127885150
514117443 -950525407
125238432 273582156
27278324 805460284
419136131 602606092
491181432 -336297462
692320446 -675844970
-492002970 357140486
761683604 836334305
- 出力例3
-
8772944624
