/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は配達員として、N 軒の家に荷物を届けることになりました。家には 1, 2, \ldots, N と番号が付けられており、家 i の標高は V_i です。標高は家ごとに異なるとは限らず、同じ値をとることもあります。
高橋君は最初、家 1 にいます。家 1 への配達はすでに完了しており、家 1 は訪問済みの状態です。高橋君はこれから、残りの家 2, 3, \ldots, N のすべてに荷物を届ける必要があります。
配達は以下のように行います。高橋君は N - 1 回の移動を行い、各移動では、現在いる家からまだ訪問していない家をちょうど 1 軒選んで移動し、その家を訪問済みとします。移動先は隣の家である必要はなく、まだ訪問していない家であればどの家でも直接移動できます。すべての家をちょうど 1 回ずつ訪問したら配達は終了です。最後にどの家にいても構いません（家 1 に戻る必要はありません）。
家 i から家 j へ直接移動するときの移動コストは、途中にどのような家があるかによらず、次の式で定まります：
|V_i - V_j| \times |i - j|
すなわち、標高の差の絶対値と家の番号の差の絶対値の積がコストとなります。
N - 1 回の移動コストの合計を最小化してください。
制約
- 1 \leq N \leq 20
- 0 \leq V_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数である。
入力
N V_1 V_2 \ldots V_N
- 1 行目には、家の軒数を表す整数 N が与えられる。
- 2 行目には、各家の標高を表す N 個の整数 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。
出力
すべての家をちょうど 1 回ずつ訪問するための移動コストの合計の最小値を 1 行で出力せよ。
入力例 1
3 10 20 40
出力例 1
30
入力例 2
4 5 3 8 1
出力例 2
13
入力例 3
8 100 250 120 400 50 300 180 90
出力例 3
950
入力例 4
15 1000000000 0 500000000 250000000 750000000 125000000 875000000 62500000 937500000 31250000 968750000 15625000 984375000 7812500 992187500
出力例 4
1921875000
入力例 5
1 0
出力例 5
0
Score : 433 pts
Problem Statement
Takahashi is a delivery person who needs to deliver packages to N houses. The houses are numbered 1, 2, \ldots, N, and the elevation of house i is V_i. Elevations are not necessarily distinct; different houses may have the same elevation.
Takahashi starts at house 1. The delivery to house 1 is already complete, and house 1 is already marked as visited. Takahashi must now deliver packages to all remaining houses 2, 3, \ldots, N.
Deliveries are performed as follows. Takahashi makes N - 1 moves. In each move, he selects exactly one unvisited house from his current location, moves to it, and marks it as visited. The destination does not need to be an adjacent house; he can move directly to any unvisited house. The delivery is complete once all houses have been visited exactly once. It does not matter which house he ends at (he does not need to return to house 1).
The cost of moving directly from house i to house j is determined by the following formula, regardless of what houses lie in between:
|V_i - V_j| \times |i - j|
In other words, the cost is the product of the absolute difference in elevations and the absolute difference in house numbers.
Minimize the total cost of the N - 1 moves.
Constraints
- 1 \leq N \leq 20
- 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N V_1 V_2 \ldots V_N
- The first line contains an integer N, representing the number of houses.
- The second line contains N integers V_1, V_2, \ldots, V_N separated by spaces, representing the elevation of each house.
Output
Print on a single line the minimum total movement cost required to visit all houses exactly once.
Sample Input 1
3 10 20 40
Sample Output 1
30
Sample Input 2
4 5 3 8 1
Sample Output 2
13
Sample Input 3
8 100 250 120 400 50 300 180 90
Sample Output 3
950
Sample Input 4
15 1000000000 0 500000000 250000000 750000000 125000000 875000000 62500000 937500000 31250000 968750000 15625000 984375000 7812500 992187500
Sample Output 4
1921875000
Sample Input 5
1 0
Sample Output 5
0