石子堆问题
✏️ 1、任意合并【链接】
有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动任意的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成1堆的最小花费和最大花费。
特点:合并的是任意两堆,直接贪心即可,每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。
// 最小花费
int mergeStones(vector<int> &nums){
if(nums.empty())
return 0;
sort(nums.begin(), nums.end());
int idx = 0;
int res = 0;
while(idx < nums.size() - 1){
nums[idx] += nums[idx + 1];
res += nums[idx];
nums[idx + 1] = 0;
int tmp = nums[idx];
int i = idx + 1;
for(; i < nums.size() && nums[i] < tmp; ++i){
nums[i - 1] = nums[i];
}
nums[i - 1] = tmp;
while(nums[idx] == 0)
idx++;
}
return res;
}
// 最大花费
int getMax(vector<int> &nums){
sort(nums.begin(), nums.end());
int res = 0;
for(int i = nums.size() - 1; i > 0; --i){
res += nums[i - 1] * nums[i];
nums[i - 1] += nums[i];
}
return res;
}
✏️ 2、相邻合并【链接】(超时,超空间)
在一个操场上摆放着一排 N 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将 N 堆石子合并成一堆的最小得分。
我们熟悉矩阵连乘,知道矩阵连乘也是每次合并相邻的两个矩阵,那么石子合并可以用矩阵连乘的方式来解决。设 表示第 到第 堆石子合并的最优值, 表示前 堆石子的总数量。那么就有状态转移公式: ,且 时 。
动态规划:阶段、状态和决策,三者应该从外到里循环。
阶段v:石子的每一次合并过程,先两两合并,再三三合并,…最后N堆合并
状态:每一阶段中各个不同合并方法的石子合并总得分。
决策:把当前阶段的合并方法细分成前一阶段已计算出的方法,选择其中的最优方案
具体来说我们应该定义一个数组 用来表示合并方法, 表示从第 堆开始数 堆进行合并的最优得分。
int mergeStones(std::vector<int> &nums){
int len = nums.size();
int sum[len + 1];
sum[0] = 0;
int dp[len + 1][len + 1];
for(int i = 1; i <= len; ++i){
sum[i] = sum[i - 1] + nums[i - 1];
dp[i][i] = 0;
}
for(int v = 1; v < len; ++v){
for(int i = 1; i <= len - v; ++i){
int j = i + v;
dp[i][j] = INT_MAX;
for(int k = i; k < j; ++k){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
dp[i][j] += sum[j] - sum[i - 1];
}
}
return dp[1][len];
}
四边形不等式优化(超空间)
平行四边形优化是一种可以将三维DP复杂度降到 的方法,但是并不是所有的DP都适用,需要满足一定条件,如下:
四边形不等式:当决策代价函数 满足 时,称 满足四边形不等式;
区间包含的单调性:当函数 满足 时,称 关于区间包含关系单调。
如果满足以上两点,可利用四边形不等式推出最优决策 的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度降低一维。具体的实施是通过记录子区间的最优决策来减少当前的决策量。令:
即 就记录了合并第 到第 堆石子时的最优合并,记录是为了限制后面的循环范围,所以递推公式为:
证明过程:
设 表示动态规划的状态量。 有类似如下的状态转移方程: 如果对于任意的 ,有 ,那么 满足四边形不等式。
设 为 的决策量,即 ,我们可以证明, ,那么改变状态转移方程为: ;
复杂度分析:不难看出,复杂度决定于 的值,以求 为例, ,所以总复杂度是 。
证明过程见下:
设 ,对于任意 ,有 (这里以 为例,max
的类似),接下来只要证明 ,那么只有当 时才有可能有 :
因为 满足四边形不等式,所以对于 有 ,所以 ,所以 ,同理可证 ,证毕。
int mergeStones(std::vector<int> &nums)
{
int len = nums.size();
int sum[len + 1];
sum[0] = 0;
int dp[len + 1][len + 1];
int s[len + 1][len + 1];
for(int i = 1; i <= len; ++i){
sum[i] = sum[i - 1] + nums[i - 1];
dp[i][i] = 0;
s[i][i] = i;
}
for(int v = 1; v < len; ++v){
for(int i = 1; i <= len - v; ++i){
int j = i + v;
dp[i][j] = INT_MAX;
for(int k = s[i][j - 1]; k <= s[i + 1][j]; ++k){
if(dp[i][j] > dp[i][k] + dp[k + 1][j]) {
dp[i][j] = dp[i][k] + dp[k + 1][j];
s[i][j] = k;
}
}
dp[i][j] += sum[j] - sum[i - 1];
}
}
return dp[1][len];
}
GarsiaWachs
算法(AC)
GarsiaWachs
算法(AC)对于石子合并问题,有一个最好的算法,那就是GarsiaWachs
算法。时间复杂度为 。
算法步骤:设序列是stone[]
,从左往右,找一个满足 的 ,找到后合并 和 ,再从当前位置开始向左找最大的 ,使其满足 ,插到 的后面就行。一直重复,直到只剩下一堆石子。在这个过程中,可以假设 和 是正无穷的。
基本思想是通过树的最优性得到一个节点间深度的约束,之后证明操作一次之后的解可以和原来的解一一对应,并保证节点移动之后他所在的深度不会改变。具体实现这个算法需要一点技巧,精髓在于不停快速寻找最小的 ,即维护一个“2-递减序列”,朴素的实现的时间复杂度是 ,但可以用一个平衡树来优化,使得最终复杂度为 。
int mergeStones(std::vector<int> &nums){
int ans = 0;
int len = nums.size();
int cnt = len - 3;
while(cnt--){ // len - 2个石子堆总共合并 len - 3 次
int tmp = 0;
int i = 2;
for(; i < len - 1; ++i){
if(nums[i - 1] <= nums[i + 1]){
tmp = nums[i - 1] + nums[i];
ans += tmp;
break;
}
}
int j = i - 1;
// 将 tmp 插入到合适的位置
for(; nums[j - 1 ] < tmp; j--)
nums[j] = nums[j - 1];
nums[j] = tmp;
// 删除第 i 个元素
nums.erase(nums.begin() + i); // 这样写就不超时,下面的写法就超时
// for(j = i; j < len - 1 ; j++)
// nums[j] = nums[j + 1];
len--;
}
return ans;
}
int main(){
int n;
cin >> n;
vector<int> nums(n + 2);
nums[0] = INT_MAX; // 两头加两个正无穷,有助于处理边界条件
int i = 1;
while(i <= n){
cin >> nums[i];
++i;
}
nums[n + 1] = INT_MAX;
cout << mergeStones(nums);
return 0;
}
有 N 堆石头排成一排,第 i 堆中有 stones[i]
块石头。每次移动(move)需要将连续的 K 堆石头合并为一堆,而这个移动的成本为这 K 堆石头的总数。找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1 。
✏️ 3、环形合并【链接】
在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。
设 表示第 堆开始合并 堆石子的最优值, 表示第 堆到第 堆石子的总数量。那么就有状态转移公式: ,且 时 。
是 和 之间的一个数
因为是环形,所以要将一维数组收尾相连,所以计算第 堆应该表示成: ,注意这里不能想当然的以为 可以和外面的1约掉就变成 ,这里是因为数组的下标是从1开始的,前者可以保证不取到0。
然后求 的最小解, 。
int sum(std::vector<int> &nums, int i, int j){
int ans = 0;
for(; j > 0; j--, i++){
if(i > nums.size() - 1)
i %= (nums.size() - 1);
ans += nums[i];
}
return ans;
}
pair<int, int> DynamicProgramming::mergeStones_ii(std::vector<int> &nums){
int len = nums.size();
int dp_min[len][len];
int dp_max[len][len];
for(int i = 1; i < len; i++){
dp_min[i][1] = 0; // 没有合并则花费为0
dp_max[i][1] = 0;
}
for(int j = 2; j < len; ++j){
for(int i = 1; i < len; ++i){
dp_min[i][j] = INT_MAX;
dp_max[i][j] = INT_MIN;
for(int k = 1; k < j; k++){
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[(i + k - 1)
% (len - 1) + 1][j - k] + sum(nums, i, j));
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[(i + k - 1)
% (len - 1) + 1][j - k] + sum(nums, i, j));
}
}
}
int mini = INT_MAX;
int maxi = INT_MIN;
for(int i = 1; i < len; i++){//从第几堆石子开始结果最小
mini = min(mini, dp_min[i][len - 1]);
maxi = max(maxi, dp_max[i][len - 1]);
}
return make_pair(mini, maxi);
}
int main(){
int n;
cin >> n;
vector<int> nums(n + 1);
nums[0] = 0;
int i = 1;
while(i <= n){
cin >> nums[i];
i++;
}
pair<int, int> res = mergeStones(nums);
cout << res.first << endl;
cout << res.second << endl;
return 0;
}
最后更新于
这有帮助吗?