区间dp 满江红中一点绿 蒟蒻求调

#include <iostream>
#include <cstring>
using namespace std;
int total;
int rock[1050];
int sum[1050];
int dp[1050][1050];
int dp_1[1050][1050];
int main()
{
    cin >> total;
    for (int i = 1; i <= total; i++)
    {
        cin >> rock[i];
        sum[i] = rock[i] + sum[i - 1];
        rock[i + total] = rock[i];
    }
    for (int i = total + 1; i <= total * 2; i++)
    {
        sum[i] = rock[i] + sum[i - 1];
    }

    for (int len = 2; len <= total; len++)
    {
        for (int left = 1; left + len - 1 <= total * 2; left++)
        {
            int right = left + len - 1;
            for (int k = left; k < right; k++)
            {
                if (dp[left][right] == 0)
                {
                    dp[left][right] = dp[left][k] + dp[k + 1][right] + sum[right] - sum[left - 1];
                }
                else
                {
                    dp[left][right] = min(dp[left][right], dp[left][k] + dp[k + 1][right] + sum[right] - sum[left - 1]);
                }
            }
        }
    }
    for (int len = 2; len <= total; len++)
    {
        for (int left = 1; left + len - 1 <= total * 2; left++)
        {
            int right = left + len - 1;
            for (int k = left; k < right; k++)
            {
                if (dp_1[left][right] == 0)
                {
                    dp_1[left][right] = dp_1[left][k] + dp_1[k + 1][right] + sum[right] - sum[left - 1];
                }
                else
                {
                    dp_1[left][right] = max(dp_1[left][right], dp_1[left][k] + dp_1[k + 1][right] + sum[right] - sum[left - 1]);
                }
            }
        }
    }
    int res = 0x3f;
    int res_1 = 0;
    for (int i = 1; i <= total + 1; i++)
    {
        res = min(res, dp[i][i + total - 1]);
        res_1 = max(res_1, dp_1[i][i + total - 1]);
    }
    cout << res << endl;
    cout << res_1 << endl;
    return 0;
}