石子合并

链接

设dp[i][j]为i-j的最小合并值,显然,它肯定等于它的所有互补的子数组的最小合并值加上这一段区间的和

也就是dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum(i,j))

由于数据量较小,三重循环也没问题

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int>nums(2 * n + 1, 0);
	vector<vector<int>>dp1(2 * n + 1, vector<int>(2 * n + 1, 0));
	vector<vector<int>>dp2(2 * n + 1, vector<int>(2 * n + 1, 0));
	vector<int>sum(2 * n + 1, 0);
	for (int i = 1;i <= n;i++) {
		cin >> nums[i];
		nums[i + n] = nums[i];
	}
	for (int i = 1;i <= 2 * n;i++) {
		sum[i] = sum[i - 1] + nums[i];
	}
	for (int i = 1;i < 2 * n;i++) {
		dp1[i][i + 1] = nums[i] + nums[i + 1];
		dp2[i][i + 1] = nums[i] + nums[i + 1];
	}
	for (int len = 2;len < n;len++) {
		for (int i = 1;i <=2 * n - len;i++) {
			int j = i + len;
			dp1[i][j] = INT_MAX;
			dp2[i][j] = 0;
			for (int k = i;k < j;k++) {
				dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + sum[j] - sum[i - 1]);
				dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]);
			}
		}
	}
	int ans1 = dp1[1][n], ans2 = dp2[1][n];
	
	for (int i = 1;i <= n;i++) {
		ans1 = min(ans1, dp1[i][i + n - 1]);
		
		ans2 = max(ans2, dp2[i][i + n - 1]);
	}
	cout << ans1 << '\n';
	cout << ans2 << '\n';
}

时间复杂度:O(n³)

空间复杂度:O(n²)