蓝桥杯算法提高VIP-合并石子 （C++代码）

        朴素区间 Dp O(n^3)，这题需要四边形不等式优化成 O(n^2) 。

参考代码:

#ifndef LOCAL
	#include <bits/stdc++.h>
#endif
const int Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'C' && o != 'D'); return o;
	}
}
using namespace IO;

const int SIZE = 1E3 + 7, Mod = 998244353;
int pre[SIZE], Arr[SIZE], Dp[SIZE][SIZE], w[SIZE][SIZE];

int main() {
	int N = read();
	for (int pos = 1; pos <= N; pos++)
		Arr[pos] = read(), w[pos][pos] = pos;
	for (int pos = 1; pos <= N; pos++)
		pre[pos] = pre[pos - 1] + Arr[pos];
		
	for (int Len = 2; Len <= N; Len++) {
		for (int L = 1, R = L + Len - 1; L <= N - Len + 1; L++, R = L + Len - 1) {
			Dp[L][R] = Inf;
			int Rm = L + Len - 1;
			for (int K = w[L][Rm - 1]; K <= w[L + 1][Rm]; K++)
				if (Dp[L][R] > Dp[L][K] + Dp[K + 1][R] + pre[R] - pre[L - 1])
					Dp[L][R] = Dp[L][K] + Dp[K + 1][R] + pre[R] - pre[L - 1], w[L][Rm] = K;
		}
	}
	printf("%d\n", Dp[1][N]);
}