No.2759 Take Pictures, Elements?
タグ : / 解いたユーザー数 87
作問者 :
aplysiaSheep
Story
Today is the school trip. Latte has brought along an old single-lens reflex camera that looks rather expensive.However, this camera has quite a narrow shooting range. Even so, in order to create youthful memories, he absolutely wants to capture his best friends in pictures.
It is troublesome, but he will spare no effort to photograph each of his best friends one by one, so he has decided to do his best to take the pictures.
Problem Statement
There are $N$ boxes $A$. The $i$-th box from the left is called box $i$, and the element inside box $i$ is called $A_i$. There is also a machine that refers to any $1$ of these boxes, and the machine is currently pointing at box $1$.
This machine can be moved to the box immediately to the right (if it exists) or the box immediately to the left (if it exists). The machine is also equipped with a mechanism for photographing the contents of a box.
Strictly speaking, Latte can perform any of the following operations independently.
- For $1\le i\le N$, choose one of the following and decide whether to perform the operation. Performing it costs $1$, and not performing it costs nothing.
- If $2\le i\le N$, move to box $i-1$.
- If $1\le i\le N-1$, move to box $i+1$.
By repeatedly performing the above operations from now on, he wants to photograph $Q$ elements $B_1,B_2,\dots,B_Q$ using the machine (under the constraints of this problem, it is guaranteed that all the elements can be photographed by moving the machine).
Note that after performing an operation $1$ time, the position the machine refers to carries over. See the sample input and output for details.
What is the minimum possible total cost required to photograph $B_1,B_2,\dots,B_Q$ in this order?
Input and Constraints
$N\ Q$ $A_1\ A_2\ \dots\ A_N$ $B_1\ B_2\ \dots\ B_Q$
- $1\le N\le 10^3$
- $1\le Q\le 10^3$
- $1\le A_i,B_j\le 10^9$
- For every $1\le j\le Q$, there exists (at least one) $k$ such that $B_j=A_k$
- All input values are integers
Output
Output the answer.
Sample
Sample 1
Input
5 4 3 7 1 9 2 1 2 3 7
Output
9
- To capture $1$, move right exactly $2$ times from box $1$ and take a picture. The required cost is $2$, and the current position is box $3$.
- To capture $2$, move right exactly $2$ times from box $3$ and take a picture. The required cost is $2$, and the current position is box $5$.
- To capture $3$, move left exactly $4$ times from box $5$ and take a picture. The required cost is $4$, and the current position is box $1$.
- To capture $7$, move right exactly $1$ time from box $1$ and take a picture. The required cost is $1$.
Sample 2
Input
3 5 7 1 10 7 7 7 7 7
Output
0
There are cases where all the elements can be photographed without any movement at all.
Sample 3
Input
3 2 1 1 2 2 1
Output
3Note that the elements of $A_i,B_i$ are not necessarily pairwise distinct.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。