python

7.0 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 282. 石子合并

一、题目描述

设有 N 堆石子排成一排，其编号为 1,2,3,…,N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2，我们可以先合并 1、2 堆，代价为 4，得到 4 5 2，又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式 第一行一个数 N 表示石子的堆数 N。

第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出格式 输出一个整数，表示最小代价。

数据范围 1≤N≤300

输入样例：

4
1 3 5 2

输出样例：

二、思考过程

1、尝试一维描述

如果用一维的方式来描述前面的状态:f[i]。描述什么呢？似乎应该是从第1堆到第i堆的 最小代价，如果能行的通，没有人会愿意把问题复杂化，再整什么二维概念了。

下面采用 实例法 描述一下最简问题，看看这样设计的状态描述办法会不会有问题：

如果有1堆石子，那么f[1]=0。为啥呢？一堆石子和谁合并啊，没的合并哪来的代价呢？
如果有2堆石子，那么f[2]=a[1]+a[2]。为啥呢？一共两堆，不合并它们两个还能合并谁，代价也没啥最不最小了，就是两堆石子的个数和。
如果有3堆石子，那么就有点意思了，可以[(1)+(2)]+(3)，也可以(1)+[(2)+(3)],这时用f[i]怎么表示呢？我们发现，此时无法描述出[(1)+(2)]和[(2)+(3)]，这是一个段的概念，一维的描述不出来！

2、尝试二维描述

思考二维的描述法，比如f[i][j],描述就是从i堆到j堆的最小代价，依然是用最简例子思考一下：

如果有1堆石子，那么f[1][1]=0,其实f[2][2]=0,f[3][3]=0,...这个好理解吧，自己独立一堆，也不和别人合并，就不需要搬啊，哪来的成本？
如果有2堆石子，那么f[1][2]=a[1]+a[2]。
如果有3堆石子，[(1)+(2)]+(3)，也可以(1)+[(2)+(3)] 那么是不是就应该有下面的式子呢：
```
\large f[1][3]=min(f[1][2]+f[3][3],f[1][1]+f[2][3])
```
结论是错误的: 为什么呢？你想啊，你提前把代价最小的两堆预备好了，就完事了吗？你就啥都不用干了？天底下哪有那么好的事！你还需要把它们两堆合并一次，代价就是这两堆的总石子个数，所以下面的式子才是 正确的：
```
\large f[1][3]=min(f[1][2]+f[3][3],f[1][1]+f[2][3])+(a[1]+a[2]+a[3])
```

三、状态转移

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

按照DP的思考问题方式，先想一个普通的场景：求从i堆合并到j堆的最小代价，我们无法一眼看到头找出最优解，但我们假设现在已经取得到f[i][j]，也就是假设我们知道了从i堆到j堆的代价最小值，那么这个结果值是从哪种情况下转移而来呢？因为按照石子合并的规则，石子是按两堆搬运后才能减少一堆，所以我们把i \sim j堆合并成一堆，它的前序状态必然是这样的：

\huge i \sim  k \sim   j

我们可以枚举倒数第二步情况，逐个在[i,j)范围内讨论k的不同取值，看看哪个结果最小，就能计算出f[i][j]的最小值。

思考:为什么k的范围是[i,j)?也就是左包右不包呢？为什么右不能包呢？回头看一下 关键点：

如果k=i，表示左边连续部分是1个，其余的是右边部分。

如果k=j,表示全是左边的，右边没有，这肯定不可能，这叫啥分界点

总结： i和j区间内合并的最小代价，其实是在引入k,其中i<=k<j后，考查每一个k作为中间节点来合并i\sim j的最小代价。

每一轮合并的代价增加值=区间内的石子数量。

优化：如果每次都重新计算区间内的石子数量和，性能差，用前缀和优化

\large f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1])

四、区间 `DP` 模版

所有的区间dp问题枚举时:

第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；
第二维枚举起点 i （右端点 j 计算获得，j = i + len - 1）

模板代码

memset(f, 0x3f, sizeof f);  //预求最小，先设最大
for (int i = 1; i <= n; i++)f[i][i] = 0;//第i堆与第i堆是不需要合并的，代价为0

...

for (int len = 2; len <= n; len++) {         // 区间长度,Q:为什么长度从2开始？因为1个的，上面初始化时就处理完了
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        
        for (int k = i; k < j; k++)         // 枚举分割点，构造状态转移方程
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + w[i][j]);
    }
}

五、实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;
const int INF = 0x3f3f3f3f;

int n;
int s[N];    // 前缀和
int f[N][N]; // 表示将i到j合并成一堆的方案的集合,属性：最小值
// 石子合并
int main() {
    cin >> n;
    // 一维前缀和,直接略过了a[i]数组，只用了一个s[i]数组保存前缀和
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

    memset(f, 0x3f, sizeof f);                // 预求最小，先设最大
    for (int i = 1; i <= n; i++) f[i][i] = 0; // 第i堆与第i堆是不需要合并的，代价为0

    // 区间DP模板
    for (int len = 1; len <= n; len++)           // 枚举区间长度
        for (int i = 1; i + len - 1 <= n; i++) { // 枚举区间左端点,右端点计算获取，保证右端点不出界
            int j = i + len - 1;                 // 区间的右端点
            // 枚举中间点k
            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]);
        }
    cout << f[1][n] << endl;
    return 0;
}

7.0 KiB Raw Permalink Blame History Unescape Escape