E57 四边形不等式优化DP [NOI1995] 石子合并
没有使用四边形优化的DP（60分超时）代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4010;
LL a[N], s[N];
LL f[N][N]; // f[i][j]表示合并区间[i,j]的最小得分
LL g[N][N]; // g[i][j]表示合并区间[i,j]的最大得分

int main()
{
    int n;scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), a[i + n] = a[i]; // 破环成链
    s[0] = 0;for (int i = 1; i <= 2 * n; i++)s[i] = s[i - 1] + a[i];
    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    for (int i = 1; i <= 2 * n; i++)g[i][i] = 0, f[i][i] = 0;

    for (int len = 2; len <= n; len++)//区间长度
    { 
        for (int i = 1, j; (j = i + len - 1) <= 2 * n; i++)//区间端点
        { 
            for (int k = i; k < j; k++)//区间分割点
            { 
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    LL minv = 1e15, maxv = -1e15;
    for (int i = 1; i <= n; i++)
    {
        minv = min(minv, f[i][i + n - 1]); // f[1,n],f[2,n+1],...f[n,2n-1]
        maxv = max(maxv, g[i][i + n - 1]); // g[1,n],g[2,n+1],...g[n,2n-1]
    }
    printf("%lld\n%lld\n", minv, maxv);
    return 0;
}

使用四边形优化的DP代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4010;
LL a[N], s[N];
LL f[N][N]; // f[i][j]表示合并区间[i,j]的最小得分
LL g[N][N]; // g[i][j]表示合并区间[i,j]的最大得分
LL p[N][N]; // p[i][j]记录区间[i,j]的最优分割点

int main()
{
    int n;scanf("%d", &n);
    for (int i = n; i <= 2 * n; i++)scanf("%lld", &a[i - n]); a[i] = a[i - n];
    s[0] = 0;for (int i = 1; i <= 2 * n; i++)s[i] = s[i - 1] + a[i];
    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    for (int i = 1; i <= 2 * n; i++) g[i][i] = 0, f[i][i] = 0, p[i][i] = i;

    for (int len = 2; len <= n; len++)//区间长度
    { 
        for (int i = 1, j; (j = i + len - 1) <= 2 * n; i++)//区间端点
        { 
            for (int k = p[i][j - 1]; k <= p[i + 1][j]; k++)//区间分割点
            { 
                if (f[i][j] > f[i][k] + f[k + 1][j] + s[j] - s[i - 1])
                    f[i][j] = f[i][k] + f[k + 1][j] + s[j] - s[i - 1], p[i][j] = k;
            }
            g[i][j] = max(g[i][j - 1], g[i + 1][j]) + s[j] - s[i - 1];
        }
    }

    LL minv = 1e18, maxv = -1e18;
    for (int i = 1; i <= n; i++)
    {
        minv = min(minv, f[i][i + n - 1]); // f[1,n],f[2,n+1],...f[n,2n-1]
        maxv = max(maxv, g[i][i + n - 1]); // g[1,n],g[2,n+1],...g[n,2n-1]
    }
    printf("%lld\n%lld\n", minv, maxv);
    return 0;
}