[AtCoder] [經典競程 90 題] 019 - Pick Two（★6）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_s
題目大意:
給定 $2N$ 個整數 $A_i$ ，現在可以花費 $|A_i - A_{i+1}|$ 的價格把相鄰兩項 $A_i$, $A_{i+1}$ 都刪掉。問把整個序列刪光的最小代價。

---

$N$ 很小，所以直接暴力 $O(N^4)$ DP 就好。$\text{DP}_{i, j}$ 代表把 $[i, j]$ 都刪掉的最小代價，轉移的話就直接枚舉刪光這個區間的最後一步是刪掉哪兩個數字就好了。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n; n <<= 1;
	vector<int> a(n);
	for (int &ai : a) cin >> ai;
	vector<vector<int>> dp(n, vector<int>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			dp[i][j] = INF;
		}
	}
	for (int len = 1; len < n; len += 2) {
		for (int i = 0; i + len < n; ++i) {
			// remove seg [i, j]
			const int j = i + len;
			for (int x = i; x <= j; x += 2) {
				for (int y = x + 1; y <= j; y += 2) {
					// remove [x, y]
					// left: [i, x - 1]
					// mid: [x + 1, y - 1]
					// right: [y + 1, j]
					int cost = 0;
					if (i <= x - 1) cost += dp[i][x - 1];
					if (x + 1 <= y - 1) cost += dp[x + 1][y - 1];
					if (y + 1 <= j) cost += dp[y + 1][j];
					dp[i][j] = min(dp[i][j], abs(a[x] - a[y]) + cost);
				}
			}
		}
	}
	cout << dp[0][n - 1] << '\n';
	return 0;
}