Part5.1 动态规划-区间类动态规划

石子合并

石子合并，区间DP
将环扩为2*n

/**@author SunLakeWalk*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")using namespace std;#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y secondtypedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int N = 1010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);int n;
int w[N];
LL s[N];
LL f1[N][N], f2[N][N];void work()
{
    cin >> n;for (int i = 1; i <= n; i ++ ){
    cin >> w[i];w[i + n] = w[i];}for (int i = 1; i <= 2 * n; i ++ )s[i] = s[i - 1] + w[i];for (int len = 2; len <= n; len ++ )for (int l = 1; l <= 2 * n - len + 1; l ++ ){
    int r = l + len - 1;f1[l][r] = 0;f2[l][r] = 1e9;for (int k = l; k < r; k ++ ){
    f1[l][r] = max(f1[l][r], f1[l][k] + f1[k + 1][r]);f2[l][r] = min(f2[l][r], f2[l][k] + f2[k + 1][r]);}f1[l][r] += s[r] - s[l - 1];f2[l][r] += s[r] - s[l - 1];}LL ans1 = 0, ans2 = 1e9;for (int i = 1; i <= n; i ++ ) ans1 = max(ans1, f1[i][i + n - 1]);for (int i = 1; i <= n; i ++ ) ans2 = min(ans2, f2[i][i + n - 1]);cout << ans2 << endl;cout << ans1 << endl;
}int main()
{
    //ios;int T = 1;// cin >> T;while (T -- ){
    work();}return 0;
}