102907: [Atcoder]ABC290 Ex - Bow Meow Optimization
Description
Score : $600$ points
Problem Statement
There are $N$ dogs numbered $1$ through $N$ and $M$ cats numbered $1$ through $M$. You will arrange the $(N+M)$ animals in a line from left to right. An arrangement causes each animal's frustration as follows:
- The frustration of dog $i$ is $A_i\times|x-y|$, where $x$ and $y$ are the numbers of cats to the left and right of that dog, respectively.
- The frustration of cat $i$ is $B_i\times|x-y|$, where $x$ and $y$ are the numbers of dogs to the left and right of that cat, respectively.
Find the minimum possible sum of the frustrations.
Constraints
- $1\leq N,M \leq 300$
- $1\leq A_i,B_i \leq 10^9$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$
Output
Print the answer as an integer.
Sample Input 1
2 2 1 3 2 4
Sample Output 1
6
Consider the following arrangement: dog $1$, cat $2$, dog $2$, cat $1$, from left to right. Then,
- dog $1$'s frustration is $1\times|0-2|=2$;
- dog $2$'s frustration is $3\times|1-1|=0$;
- cat $1$'s frustration is $2\times|2-0|=4$; and
- cat $2$'s frustration is $4\times|1-1|=0$,
so the sum of the frustrations is $6$. Rearranging the animals does not make the sum less than $6$, so the answer is $6$.
Sample Input 2
1 2 100 100 290
Sample Output 2
390
Sample Input 3
5 7 522 575 426 445 772 81 447 629 497 202 775 325
Sample Output 3
13354
Input
题意翻译
$n$ 只狗和 $m$ 支猫（编号从 $1$ 开始）排成一列，第 $i$ 只狗权值为 $a_i$，第 $i$ 只猫权值为 $b_i$。 对于一种排列方案，设第 $i$ 只狗左侧、右侧猫数目分别为 $l_i$、$r_i$，第 $i$ 只猫左侧、右侧狗数目分别为 $p_i$、$q_i$，定义此排列的不和谐度为 $(\sum_{i=1}^na_i|l_i-r_i|)+(\sum_{i=1}^mb_i|p_i-q_i|)$。 求所有排列方案中不和谐度的最小值。Output
问题描述
有编号为$1$到$N$的$N$只狗和编号为$1$到$M$的$M$只猫。你需要将这$(N+M)$只动物从左到右排成一行。一种排列方式会导致每只动物的< strong>挫败感如下：
- 狗$i$的挫败感是$A_i\times|x-y|$，其中$x$和$y$分别是该狗左边和右边的猫的数量。
- 猫$i$的挫败感是$B_i\times|x-y|$，其中$x$和$y$分别是该猫左边和右边的狗的数量。
找出挫败感之和的最小可能值。
约束条件
- $1\leq N,M \leq 300$
- $1\leq A_i,B_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入数据从标准输入给出，格式如下：
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$
输出
将答案作为一个整数输出。
样例输入1
2 2 1 3 2 4
样例输出1
6
考虑以下排列方式：狗$1$，猫$2$，狗$2$，猫$1$，从左到右。那么，
- 狗$1$的挫败感是$1\times|0-2|=2$；
- 狗$2$的挫败感是$3\times|1-1|=0$；
- 猫$1$的挫败感是$2\times|2-0|=4$；和
- 猫$2$的挫败感是$4\times|1-1|=0$，
所以挫败感之和为$6$。重新排列动物并不能使挫败感之和小于$6$，所以答案是$6$。
样例输入2
1 2 100 100 290
样例输出2
390
样例输入3
5 7 522 575 426 445 772 81 447 629 497 202 775 325
样例输出3
13354