d879: 10911 - Forming Quiz teams

d879: 10911 - Forming Quiz teams

題 意:

你 被 指 派 一 個 任 務 要 組 隊 參 加 一 個  猜 謎 比 賽 (MCA CPCI Quiz Championship)。有 $2 \times N$ 個 學 生 有 興 趣 參 加，而 你 要 把 他 們 組 成 $N$ 隊，每 隊 2 個 人。由 於 隊 友 間 需 要 在 一 起 練 習，學 生 們 都 希 望 隊 友 的 家 盡 可 能 離 自 己 的 家 近 一 些。令 $x_1$ 代 表 第 1 隊 隊 員 家 之 間 的 距 離，$x_2$ 代 表 第 2 隊 隊 員 家 之 間 的 距 離，依 此 類 推。你 必 須 要 確 保 $x_1 + x_2 + x_3 + ... + x_n$ 為最小。

solve:

位 元 DP。

記 得 先 對 每 個 人 的 距 離 預 處 理，還 有 找 第 一 個 人 的 時 候 要 從 左 找 起，不 然 會 算 到 還 未 定 義 的 距 離。

code: