「学习笔记」Garsia-Wachs 算法

引入

过程

我们看到这个题，自然而然会想到区间 DP，即朴素的做法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll r[600], g[600];
ll dp[600][600];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) {
		scanf("%lld", &r[i]);
		r[i + n] = r[i];
		g[i] = g[i - 1] + r[i];
		dp[i][i] = 0;
	}
	for (int i = n + 1; i <= 2 * n; ++ i) {
		dp[i][i] = 0;
		g[i] = g[i - 1] + r[i];
	}
	for (int l = 1; l < n; ++ l) {
		for (int i = 1, j = i + l; i < n * 2 && j <= n * 2; ++ i, j = i + l) {
			dp[i][j] = 100000000;
			for (int k = i; k < j; ++ k) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + g[j] - g[i - 1]);
			}
		}
	}
	ll minn = 0x3f3f3f3f;
	for (int i = 1; i <= n; ++ i) {
		minn = min(minn, dp[i][i + n - 1]);
	}
	printf("%lld", minn);
	return 0;
}

交上去后，你会发现，RE 了
Garsia-Wachs 算法的总时间复杂度为
= =，这个算法应用范围十分有限，因此学的价值不是很高，“会用” + “知道有这个东西” 就行了
关于上面那道引入题的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read() {
	ll x = 0;
	int fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 4e4 + 5;

int n, ans;
vector<int> g;

int merge() {
	int k = g.size() - 2;
	for (int i = 0; i <= k; ++ i) {
		if (g[i] <= g[i + 2]) {
			k = i;
			break;
		}
	}
	int tmp = g[k] + g[k + 1];
	g.erase(g.begin() + k);
	g.erase(g.begin() + k);
	int t = -1;
	for (int i = k - 1; i >= 0; -- i) {
		if (g[i] >= tmp) {
			t = i;
			break;
		}
	}
	g.insert(g.begin() + t + 1, tmp);
	return tmp;
}

int main() {
	n = read();
	for (int i = 1; i <= n; ++ i) {
		g.emplace_back(read());
	}
	for (int i = 1; i < n; ++ i) {
		ans += merge();
	}
	printf("%d\n", ans);
	return 0;
}