先枚举区间长度的一种 DP

石子合并

题意： 合并 堆石子，每次只能合并相邻的两堆石子，求最小代价

分析： 最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

不妨把当前合并的石子堆的大小作为 DP 的阶段

这样 表示初值，即每个堆只有一个石子； 表示终值，即一个堆中有所有的石子

这种阶段设置方法保证了我们每次合并两个区间时，他们的所有子区间的合并费用都已经被计算出来了

为了优化求合并费用这个过程，可以先求一个前缀和

状态表示： 表示将 到 这一段石子合并成一堆的最小花费

状态计算： 时， 其中 时， (合并一堆石子代价为 0)

复杂度： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>

using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

int main() {
    int n;
    cin >> n;

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

    memset(f, 0x3f, sizeof f);
    // 区间 DP 枚举套路：长度+左端点
    for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数
        for (int i = 1; i + len - 1 <= n; i ++) {
            int j = i + len - 1; // 自动得到右端点
            if (len == 1) {
                f[i][j] = 0;  // 边界初始化
                continue;
            }

            for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout << f[1][n] << endl;


    return 0;
}

环形石子合并

题意：给定 个石子的分数 ，且石子是环形放置的(在给定的顺序上，同时满足 和 也是相邻的)

规定每次只能合并相邻的两堆石子，形成一个新的石子堆，合并的费用是两个石子堆的分数之和

求解两个方案：把这 堆石子合并为一堆，且费用(最大+最小)的方案

分析： 与石子合并几乎一致，区别在于变为了环形，可以考虑将其扩展为正常长度 的两倍，此时做一次正常的区间 DP，可以发现从 到 的方案包含了所有的可能

其余与上一题保持一致即可

复杂度： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 205, M = N << 1, INF = 0x3f3f3f3f;

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
        w[i + n] = w[i];  // 扩展到2*n的空间
    }

    for (int i = 1; i <= 2 * n; 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 < 2 * n; l ++ )
        {
            int r = l + len - 1;
            if (len == 1)  f[l][l] = g[l][l] = 0;
            else
                for (int k = l; k + 1 <= 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 maxv = -2e9, minv = 2e9;

    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;
    cout << maxv << endl;
    return 0;
}

能量项链

题意：给定 个能量石, 每个能量石有一个二元属性 ，相邻的属性相同, 即

魔法石是顺序且环形摆放的， 每次可以融合相邻两个魔法石

融合两个能量石 , 所产生的能量为

求将所有的能量石连接成为一条项链时产生的最大能量值

分析： 首先，环形石子一样，可以利用开 的空间进行 DP 解决环形问题

然后考虑一下不同点

  • 区间的长度要从 2 枚举到 ，因为 个点对应了 个数

  • 环形石子中，我们将区间 分为了 和 ，在这里分割点 k 要被同时分到左右区间中，就是将区间 分为了 和

  • 本题中最差的情况也一定是 的所以可以省去一个初始化的过程，直接从 3 开始枚举

状态表示： 表示左端石头的左参数是 ，右端石头的右参数是 的最大能量

状态计算：

复杂度： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 105, M = N << 1;

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

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;
            // 省去了len=2(一个点)时初始化为0
            for (int k = l + 1; k < r; k ++ )
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }

    int ans = 0;
    for(int i = 1; i <= n; i ++ )  ans = max(ans, f[i][i + n]);
    cout << ans << endl;

    return 0;
}

加分二叉树

题意： 给定一个含有 个结点的二叉树的中序遍历序列中每个节点的权值

定义 一棵子树的分数 = 左子树的分数 × 右子树的分数 + 根节点的权值

额外规定空树的分数为 1 求一种满足该中序遍历的建树方案，使得整棵树的分数最大

分析： 将二叉树表示为区间，在状态转移时枚举分割点，将二叉树分为左右两个区间加上根节点

即将 表示的二叉树集合按根节点分类，则根节点在 时的最大得分即为

，则 即为遍历 所取到的最大值。

在计算每个状态的过程中，记录每个区间的最大值所对应的根节点编号

那么最后就可以通过 DFS 求出最大加分二叉树的前序遍历

状态表示： 表示中序遍历是 的所有二叉树的得分的最大值

状态计算：

复杂度： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

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

void dfs(int l, int r)
{
    if(l > r)  return;

    int k = root[l][r];  //
    cout << k << " ";  // 前序遍历先输出根节点
    dfs(l, k - 1);
    dfs(k + 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;

            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 score = left * right + w[k];  // 计算加分
                if (l == r) score = w[k];
                if (f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;  // 记录节点
                }
            }
        }

    cout << f[1][n] << endl;
    dfs(1, n);  // 输出前序遍历
    return 0;
}

记忆化搜索的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

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

int dp(int l, int r)
{
    if (~f[l][r]) return f[l][r];  // 记忆化
    if (l == r)  return root[l][r] = l, f[l][r] = w[l];
    if (l > r) return f[l][r] = 1;
    int score = -0x3f3f3f3f;
    for (int i = l; i <= r; i ++ )
    {
        int t = dp(l, i - 1) * dp(i + 1, r) + w[i];
        if (t > score)
            score = t, root[l][r] = i;
    }
    return f[l][r] = score;
}

void dfs(int l, int r)
{
    if(l > r)  return;

    int k = root[l][r];  //
    cout << k << " ";  // 前序遍历先输出根节点
    dfs(l, k - 1);
    dfs(k + 1, r);
}

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

    memset(f, -1, sizeof f);

    cout << dp(1, n) << endl;
    dfs(1, n);  // 输出前序遍历
    return 0;
}

凸多边形的划分

题意： 给定 个点的凸多边形中每个顶点的权值 我们可以把该 凸多边形 划分成 个 三角形(三角形不能相交，这样就能保证是 了)

每次划分三角形的费用为三个顶点权值的乘积

求一个划分方案的使得费用总和最小

分析： 这是一个经典的图形学问题 —> 三角剖分

对于一个凸多边形考虑将其视作一个区间，那么枚举分割点 (种情况) 后， 如下图所示

可以将其划分为两个线段和一个三角形，这样就将该问题转化为了经典的区间 DP 问题 + 高精度

策略： 可以先打出一个不是高精度的，测过样例后再改为高精度，这样不易出错

image-20220715170207604

状态表示： 当前划分到的多边形的左端点是 ，右端点是 的方案数

状态计算：

时间复杂度： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 55;

int n;
int w[N];
vector<int> f[N][N];

bool cmp(vector<int> &a, vector<int> &b)
{
    if (a.size() != b.size()) return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i -- )
        if (a[i] != b[i])
            return a[i] < b[i];
    return true;
}
vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i ++ )
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}
vector<int> mul(vector<int> a, LL b)
{
    vector<int> c;
    LL t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += b * a[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}

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

    //此处初始状态f[l][l+1] = 0 初始就是空vector，不用额外设置
    for (int len = 3; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k ++ )
            {
                 auto new_val = mul(mul({w[l]}, w[k]), w[r]);
                new_val = add(add(new_val, f[l][k]), f[k][r]);
                if (f[l][r].empty() || cmp(new_val, f[l][r])) f[l][r] = new_val;
            }
        }

    auto ans = f[1][n];
    for (int i = ans.size() - 1; i >= 0; i -- ) cout << ans[i];
    return 0;
}

棋盘分割

题意： 将一个 的棋盘进行分割, 棋盘的每个小方格都有一个权值

每次我们可以对棋盘进行一次横或竖切，将棋盘分成两块矩形的子棋盘

分割完一次后，我们可以选择两个子棋盘中的一个再继续递归操作(我们只能保留一个继续分割)

如图：

现需要把棋盘按照上述分割方案，分成 块( 次划分操作)

求一个划分方案，使得各子棋盘的总分的均方差最小

均方差公式：

其中平均值，为第块矩形棋盘的总分

分析：

为了求解方便，先将 平方转换得到，假设分为 块，其中每一块的总分为

$$

$$

对于一个区域， 我们可以将其用左上 和右下 的两个点表示出来，

我们可以将 DP 的值表示为该区域内的 ，

我们通过一个五维的状态表示 记录分割次数和左上角和右下角

那么对于一个状态, 可以由这样两个子状态转移过来，就是二维状态下的区间 DP，再枚举下横切还是竖切即可

（选取上半部分继续分割时，加上的是下半部分的 )

在计算块内总分这一步可以预处理出二维的前缀和来 求解

定义 get() 函数表示一个区域内的

状态表示： 将 和 之间的子矩阵分成 块的最小均方差

状态计算： 记

  • 枚举横切：在 和 之间枚举分界点

  • 枚举纵切：在 和 之间枚举分界点

复杂度： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

const int N = 16, INF = 0x3f3f3f3f;
int n, m = 8;
int s[N][N];
double f[N][N][N][N][N];
double X;

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

double dp(int k, int x1, int y1, int x2, int y2)
{
    double &t = f[k][x1][y1][x2][y2];  // 记忆化搜索
    if(t >= 0)  return t;
    if(k == n)  return t = get(x1, y1, x2, y2);  // 没有切割的状态

    t = INF;

    for (int x = x1; x < x2; x ++ )  // 枚举横切
    {
        t = min(t, dp(k + 1, x1, y1, x, y2) + get(x + 1, y1, x2, y2));
        t = min(t, dp(k + 1, x + 1, y1, x2, y2) + get(x1, y1, x, y2));
    }

    for (int y = y1; y < y2; y ++ )  // 枚举纵切
    {
        t = min(t, dp(k + 1, x1, y1, x2, y) + get(x1, y + 1, x2, y2));
        t = min(t, dp(k + 1, x1, y + 1, x2, y2) + get(x1, y1, x2, y));
    }

    return t;
}

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];
        }

    memset(f, -1, sizeof f);
    // 计算均值
    X = (double) s[m][m] / n;
    // 记忆化搜索
    cout << fixed << setprecision(3) << sqrt(dp(1, 1, 1, 8, 8) / n) << endl;

    return 0;
}