# 洛谷 P1880 [NOI1995]石子合并

 123456789101112131415161718192021222324252627282930313233343536373839404142 #include #include #include #include using namespace std; int n; int arr[205]; int presum[205]; int fMax[205][205], fMin[205][205]; int dfsMax(int l, int r) {     if (l == r)return 0;     if (fMax[l][r] != 0)return fMax[l][r];     int dIJ = presum[r] - presum[l - 1];     int mmax = 0;     for (int k = l; k < r; k++) mmax = max(mmax, dfsMax(l, k) + dfsMax(k + 1, r) + dIJ);     return fMax[l][r] = mmax; } int dfsMin(int l, int r) {     if (l == r)return 0;     if (fMin[l][r] != 0)return fMin[l][r];     int dIJ = presum[r] - presum[l - 1];     int mmin = 0x7fffffff;     for (int k = l; k < r; k++)mmin = min(mmin, dfsMin(l, k) + dfsMin(k + 1, r) + dIJ);     return fMin[l][r] = mmin; } int main(){     cin >> n;     for (int i = 1; i <= n; i++)cin >> arr[i];     for (int i = n + 1; i <= 2*n; i++)arr[i] = arr[i - n];     for (int i = 1; i <= 2 * n; i++)presum[i] = presum[i - 1] + arr[i];     int mmin = 0x7fffffff;     for (int i = 1; i <= n; i++) {         mmin = min(mmin, dfsMin(i, i + n - 1));     }     cout << mmin << endl;     int mmax = 0;     for (int i = 1; i <= n; i++) {         mmax = max(mmax, dfsMax(i, i + n - 1));     }     cout << mmax << endl; }