문제에서 요구하는 것은 다음과 같이 요약할 수 있다.

• 점수는 사람마다 매기는 것이 아니라 전체로 따진다.
• i번 사람은 A[i] 또는 B[i]에서 최대 한 개를 선택할 수 있고, 선택한 것을 점수로 얻는다.
• i번 사람과 j번 사람이 하나씩 골랐고 다른 것을 선택했다면, H[i, j]만큼 점수를 감점 당한다.
• 전체 점수가 최대가 되도록 골라주자.

수식으로 적어보자. 우선 수식으로 표현하기 위해 다음과 같이 정의하자.

$$\mathbf{U} := \left\{\texttt{1번부터 N번까지의 사람들 번호}\right\} \\ \mathbb{A} := \left\{i | i\texttt{번째 사람이 }A[i]\texttt{를 선택했다.} \right\} \\ \mathbb{B} := \left\{i | i\texttt{번째 사람이 }B[i]\texttt{를 선택했다.} \right\} \\ $$

그리고 다음을 만족해야 한다.

$$(\mathbb{A} \cup \mathbb{B}) \subset \mathbf{U} \\ (\mathbb{A} \cap \mathbb{B}) = \phi$$

전체 점수는 다음과 같이 표현할 수 있고, 등식이 성립한다.

$$\begin{align} S = & \sum_{i \in \mathcal{A}}{A[i]} + \sum_{i \in \mathcal{B}}{B[i]} - \sum_{i \in \mathbb{A}} \sum_{j \in \mathbb{B}} H[i, j] \\ = & \sum_{i \in \mathbf{U}}{A[i] + B[i]} - \sum_{i \in \mathcal{A}^{\textrm{C}}}{A[i]} - \sum_{i \in \mathcal{B}^{\textrm{C}}}{B[i]} - \sum_{i \in \mathbb{A}} \sum_{j \in \mathbb{B}} H[i, j] \\ = & \sum_{i \in \mathbf{U}}{\left(A[i] + B[i]\right)} - \underbrace{\left\{\sum_{i \in \mathcal{A}^{\textrm{C}}}{A[i]} + \sum_{i \in \mathcal{B}^{\textrm{C}}}{B[i]} + \sum_{i \in \mathbb{A}} \sum_{j \in \mathbb{B}} H[i, j]\right\}}_{\ast} \end{align}$$

우리가 하고자 하는 것은 S$S$를 최대화 하는 것이다. 그렇다면 위 식의 \ast$\ast$ 부분을 최소화 하는 문제로 여길 수 있다.

• 작업중