AT_arc129_e.[ARC129E] Yet Another Minimization

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

すぬけ君想要构造一个长度为 $N$ 的整数序列 $x=(x_1,x_2,\cdots,x_N)$ 。对于每个 $i$ （ $1 \leq i \leq N$ ）， $x_i$ 有 $M$ 种可选值，其中第 $k$ 种值为 $A_{i,k}$ 。选择 $A_{i,k}$ 时，需要花费 $C_{i,k}$ 的代价。

此外，确定 $x$ 之后，对于每一对 $i,j$ （ $1 \leq i < j \leq N$ ），还需要额外支付 $|x_i-x_j| \times W_{i,j}$ 的代价。

请你求出所有可能的总代价的最小值。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$ $A_{1,1}$ $C_{1,1}$ $A_{1,2}$ $C_{1,2}$ $\cdots$ $A_{1,M}$ $C_{1,M}$ $A_{2,1}$ $C_{2,1}$ $A_{2,2}$ $C_{2,2}$ $\cdots$ $A_{2,M}$ $C_{2,M}$ $\cdots$ $A_{N,1}$ $C_{N,1}$ $A_{N,2}$ $C_{N,2}$ $\cdots$ $A_{N,M}$ $C_{N,M}$ $W_{1,2}$ $W_{1,3}$ $\cdots$ $W_{1,N-1}$ $W_{1,N}$ $W_{2,3}$ $W_{2,4}$ $\cdots$ $W_{2,N}$ $\cdots$ $W_{N-1,N}$

输出格式

请输出答案。

输入输出样例

输入#1
```
3 2
1 1
5 2
2 3
9 4
7 2
8 2
1 5
3
```
输出#1
```
28
```

输入#2

10 3
19 2517
38 785
43 3611
3 681
20 758
45 4745
6 913
7 2212
22 536
4 685
27 148
36 2283
25 3304
36 1855
43 2747
11 1976
32 4973
43 3964
3 4242
16 4750
50 24
4 4231
22 1526
31 2152
15 2888
28 2249
49 2208
31 3127
40 3221
47 4671
24 6 16 47 42 50 35 43 47
29 18 28 24 27 25 33 12
5 43 20 9 39 46 30
40 24 34 5 30 21
50 6 21 36 5
50 16 13 13
2 40 15
25 48
20

输出#2

输入#3
```
2 2
1 1
10 10
1 1
10 10
100
```
输出#3
```
2
```

说明/提示

限制条件

$2 \leq N \leq 50$
$2 \leq M \leq 5$
$1 \leq A_{i,1} < A_{i,2} < \cdots < A_{i,M} \leq 10^6$
$1 \leq C_{i,k} \leq 10^{15}$
$1 \leq W_{i,j} \leq 10^6$
所有输入的值均为整数

样例解释 1

如果选择 $x=(5,9,7)$ ，各项代价如下：

$x_1$ 选择 $A_{1,2}$ ，代价为 $C_{1,2}=2$ 。
$x_2$ 选择 $A_{2,2}$ ，代价为 $C_{2,2}=4$ 。
$x_3$ 选择 $A_{3,1}$ ，代价为 $C_{3,1}=2$ 。
对于 $(i,j)=(1,2)$ ，代价为 $|x_i-x_j| \times W_{i,j}=4$ 。
对于 $(i,j)=(1,3)$ ，代价为 $|x_i-x_j| \times W_{i,j}=10$ 。
对于 $(i,j)=(2,3)$ ，代价为 $|x_i-x_j| \times W_{i,j}=6$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页