← 返回题目列表

AtCoder · awc0092_d

D. 演示顺序

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥负责举办公司演讲比赛。在本次比赛中, N 员工将进行演示,每个员工都会被分配一个编号 1 to N.

每位员工 i (1 \leq i \leq N) 有一个正整数 A_i 代表他们的“演讲技巧”。

比赛中,各 N 为员工分配了唯一的演示顺序 1st 至 N第。让 P_i 表示员工所在的职位 i 呈现。然后 (P_1, P_2, \ldots, P_N) 是一个排列 (1, 2, \ldots, N)。演讲按顺序进行: 1圣, 2nd, \ldots, N第。

员工的“贡献” i 定义为 A_i \times P_i。竞赛的“总分”定义为所有员工贡献的总和:

\displaystyle\sum_{i=1}^{N} A_i \times P_i

高桥想要最大化总分。然而,青木强加了 M 限制。每个约束 k (1 \leq k \leq M) 指出“员工 U_k 必须在员工面前出现 V_k (即 P_{U_k} < P_{V_k})".

在满足所有约束的所有呈现顺序中,找到总分最大的一个,并输出最大总分。

保证存在至少一个满足所有约束的呈现顺序。

约束

  • 1 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i \leq 100 (1 \leq i \leq N)
  • 1 \leq U_k, V_k \leq N (1 \leq k \leq M)
  • U_k \neq V_k (1 \leq k \leq M)
  • 同一对 (U_k, V_k) 未给出多次。
  • 至少存在一种满足所有约束的呈现顺序(即,以员工为顶点、约束为有向边的有向图是 DAG)。
  • 所有输入值均为整数。

输入

N M
A_1 A_2 \ldots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 第一行包含 N,员工人数,以及 M,约束数量,以空格分隔。
  • 第二行包含 A_1, A_2, \ldots, A_N,每个员工的演示技巧,以空格分隔。
  • 以下 M 行包含约束。当以下情况时这些行不存在 M = 0.
  • 的 (2 + k)第行 (1 \leq k \leq M) 包含 U_k 和 V_k,以空格分隔,表示员工 U_k 必须在员工面前出现 V_k.

输出

在单行中输出满足所有约束的所有呈现顺序中的最大总分。


示例输入 1

3 1
1 2 3
1 2

示例输出 1

14

示例输入 2

3 1
3 1 2
1 3

示例输出 2

13

示例输入 3

5 3
5 3 8 1 6
4 1
4 2
3 5

示例输出 3

84

示例输入 4

8 4
10 20 30 40 50 60 70 80
1 2
3 4
5 6
7 8

示例输出 4

2040

示例输入 5

1 0
42

示例输出 5

42