P1880 [NOI1995] 石子合并

WA pts0%

最大值没问题……但最小值……

#include <bits/stdc++.h>
using namespace std;
int a[101], dp1[101][101], dp2[101][101];
int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i - 1];
	}
	memset(dp1, 0x3f, sizeof(dp1));
	memset(dp2, 0, sizeof(dp2));
	for (int i = 1; i <= n; i++){
		dp1[i][i] = 0;
		dp2[i][i] = 0;
	}
	for (int len = 2; len <= n; len++)
		for (int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			for (int k = i; k < j; k++){
				dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + a[j] - a[i - 1]);
				dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + a[j] - a[i - 1]);
			}
		}
	cout << dp1[1][n] << endl << dp2[1][n];
	return 0;
}