环形石子合并

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 404;

int n;
int w[N], s[N];
int f[N][N], g[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> w[i];
        w[i + n] = w[i]; // 断环成链
    }

    for (int i = 1; i <= n * 2; i ++) s[i] = s[i - 1] + w[i]; // 求一遍前缀和

    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);

    for (int len = 1; len <= n; len ++)
        for (int l = 1; l + len - 1 <= n * 2; l ++) // 左端点可以从1 ~ 2 * n
        {
            int r = l + len - 1;
            if (len == 1) // 合并一堆石子的代价为0
                f[l][r] = g[l][r] = 0;
            else
                for (int k = l; k < r; k ++)
                {
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
        }

    int minv = 0x3f3f3f3f, maxv = -0x3f3f3f3f;
    for (int i = 1; i <= n; i ++)
    {
        minv = min(minv, f[i][i + n - 1]);
        maxv = max(maxv, g[i][i + n - 1]);
    }

    cout << minv << endl << maxv << endl;
    return 0;
}

能量项链

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 202;

int n;
int w[N];
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> w[i];
        w[i + n] = w[i]; // 断环成链
    }

    for (int len = 3; len <= n + 1; len ++)
        for (int l = 1; l + len - 1 <= 2 * n; l ++)
        {
            int r = l + len - 1;

            for (int k = l + 1; k < r; k ++) // 不能自己和自己合并, 所以分界点从l + 1 ~ r - 1
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }

    int res = 0;
    for (int i = 1; i <= n; i ++) res = max(res, f[i][i + n]); // 枚举所有长度为n + 1的区间, 取最大值

    cout << res;
    return 0;
}

凸多边形的划分

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 55, M = 30, INF = 1e9;

int n;
int w[N];
LL f[N][N][M];

void add(LL a[], LL b[]) // 高精加法
{
    LL c[M];
    memset(c, 0, sizeof c);

    for (int i = 0, t = 0; i < M; i ++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

void mul(LL a[], LL b) // 高精乘法
{
    LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;
    for (int i = 0; i < M; i ++)
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

int cmp(LL a[], LL b[]) // 比较函数
{
    for (int i = M - 1; i >= 0; i --)
        if (a[i] > b[i]) return 1;
        else if (a[i] < b[i]) return -1;
    return 0;
}

void print(LL a[])
{
    int k = M - 1;
    while (k && !a[k]) k --;
    while (k >= 0) cout << a[k --];
    cout << endl;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    LL tmp[M];
    for (int len = 3; len <= n; len ++)
        for (int l = 1; l + len - 1 <= n; l ++)
        {
            int r = l + len - 1;
            f[l][r][M - 1] = 1; // 把最高位赋值为1

            for (int k = l + 1; k < r; k ++)
            {
                memset(tmp, 0, sizeof tmp);
                tmp[0] = w[k];
                mul(tmp, w[l]);
                mul(tmp, w[r]);
                add(tmp, f[l][k]);
                add(tmp, f[k][r]);
                if (cmp(f[l][r], tmp) > 0)
                    memcpy(f[l][r], tmp, sizeof tmp);
            }
        }

    print(f[1][n]);
    return 0;
}

加分二叉树

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 33;

int n;
int w[N];
int f[N][N], g[N][N]; // g[l][r]表示l ~ r序列中的根节点

void dp(int l, int r) // 求最优方案的先序遍历
{
    if (l > r) return ;
    int u = g[l][r];
    cout << u << ' ';
    dp(l, u - 1);
    dp(u + 1, r);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    for (int len = 1; len <= n; len ++)
        for (int l = 1; l + len - 1 <= n; l ++)
        {
            int r = l + len - 1;

            if (len == 1) f[l][r] = w[l], g[l][r] = l; // 如果为叶子节点, 那么父亲就为自己
            else
                for (int k = l; k <= r; k ++) // 枚举根节点位置
                {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r];
                    int v = left * right + w[k];
                    if (f[l][r] < v)
                        f[l][r] = v, g[l][r] = k;
                }
        }
    cout << f[1][n] << endl;
    dp(1, n);
    return 0;
}

棋盘分割

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 16, M = 9;
const double INF = 1e9;

int n, m = 8;
int s[M][M]; // 二维前缀和
double f[M][M][M][M][N];
double X; // 表示平均数

double get(int x1, int y1, int x2, int y2)
{
    double sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] - X;
    return (double)sum * sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k) // 采用记忆化搜索的方式
{
    double &v = f[x1][y1][x2][y2][k];
    if (v >= 0) return v; // 如果已经求出, 则一定为最优解, 就不用再求
    if (k == 1) // 如果不需要分割了
        return v = get(x1, y1, x2, y2);

    v = INF;
    for (int i = x1; i < x2; i ++) // 按行分割
    {
        v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));
        v = min(v, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));
    }

    for (int i = y1; i < y2; i ++) // 按列分割
    {
        v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
        v = min(v, get(x1, i + 1, x2, y2) + dp(x1, y1, x2, i, k - 1));
    }

    return v;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= m; j ++)
        {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    X = (double) s[m][m] / n;
    memset(f, -1, sizeof f); // 赋初值
    printf ("%.3lf", sqrt(dp(1, 1, m, m, n)));
    return 0;
}