石子合并（直线版+环形版）&（朴素写法+四边形优化+GarsiaWachs算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了石子合并（直线版+环形版）&（朴素写法+四边形优化+GarsiaWachs算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6779字，纯文字阅读大概需要10分钟。
内容图文
石子合并-直线版
朴素写法
最简单常见的写法就是通过枚举分割点，求出每个区间合并的最小花费，从而得到整个区间的最小花费，时间复杂度为O(n^3），核心代码如下：
for (int i = 1; i < n; i++)
{
for (int j = 1; j + i <= n; j++)
{
int e = j + i;
dp[j][e] = inf;
for (int k = j; k + 1 <= e; k++)
{
dp[j][e] = min(dp[j][e], dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1]);
}
}
}
View Code
四边形优化
对于函数f[][]（在这里可以看作数组），如果满足 f[a][c] + f[b][d] <= f[b][c] + f[a][d]，则f满足四边形不等式，即 f[i][j-1] <= f[i][j] <= f[i+1][j]
记s[i][j]表示取得dp[i][j]的最优解的分割点，稍加证明即可发现其满足四边形不等式
注意到，在朴素写法中，我们需要枚举分割点来求解：dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j] + sum[j] - sum[i-1]) {i <= k <= j ) ，而因为 s[i][j-1] <= s[i][j] <= s[i+1][j]，所以我们枚举的最优分割点s[i][j]的范围即[ s[i][j-1],s[i+1][j] ] ，所以我们枚举分割点的时候，就直接枚举区间[ s[i][j-1],s[i+1][j] ] 而不用枚举[i,j]，这样一来，时间复杂度就是O(n^2)，核心代码如下：
for (int i = 1; i <= n; i++) //枚举右端点-左端点的值
{
for (int j = 1; j + i <= n; j++) //枚举区间左端点
{
int e = j + i; //区间右端点
dp[j][e] = inf;
for (int k = s[j][e - 1]; k <= s[j + 1][e]; k++)
{
if (dp[j][e] > dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1])
{
dp[j][e] = dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1];
s[j][e] = k;
}
}
}
}
View Code?
GarsiaWachs算法
这个方法是我觉得最优的解法了，时间复杂度为O(nlogn)，比四边形优化更快，具体原理理解不足，就先贴上大佬的解析吧
解决这类问题的大概步骤是：
0.证明w满足四边形不等式，这里w是m的附属量，形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]}，此时大多要先证明w满足条件才能进一步证明m满足条件
1.证明m满足四边形不等式
2.证明s[i,j-1]≤s[i,j]≤s[i+1,j]
设序列是stone[]，从左往右，找一个满足stone[k-1] <= stone[k+1]的k，找到后合并stone[k]和stone[k-1]，再从当前位置开始向左找最大的j，使其满足stone[j] > stone[k]+stone[k-1]，插到j的后面就行。一直重复，直到只剩下一堆石子就可以了。在这个过程中，可以假设stone[-1]和stone[n]是正无穷的。
举个例子：186 64 35 32 103
因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面，得到：186 67 64 103,现在由5个数变为4个数了，继续：186 131 103，现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）234 186，最后得到420。最后的答案呢？就是各次合并的重量之和，即420+234+131+67=852。
基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变。具体实现这个算法需要一点技巧，精髓在于不停快速寻找最小的k，即维护一个“2-递减序列”朴素的实现的时间复杂度是O(n*n)，但可以用一个平衡树来优化，使得最终复杂度为O(nlogn)。
（解析出自：https://blog.csdn.net/bao___zi/article/details/81913096）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>
#define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 1e9 + 7;
const ll mod = 1e9 + 7;
const int Max = 4e4 + 10;
int n;
int val[40010], len;
int sum;
void combine(int k)
{
int add = val[k] + val[k - 1]; //合并
sum += add; //累加合并的值
for (int i = k; i < len; i++) //k之后的数前移一个位置
{
val[i] = val[i + 1];
}
len--; //合并后，总长度减一
int pos = k - 1;
while (pos > 0 && val[pos - 1] < add) //找到k前的第一个大于add的数
{
val[pos] = val[pos - 1];
pos--;
}
val[pos] = add; //插入第一个比add大的数后面
while (pos >= 2 && val[pos] >= val[pos - 2])
{
int res = len - pos; //记录pos之后的元素个数，相当于跳过了，后面要补上
combine(pos - 1); //合并
pos = len - res; //后面那一段仍然跳过
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", val + i);
}
len = 1; //跳过第一个
sum = 0;
for (int i = 1; i < n; i++)
{
val[len++] = val[i]; //将值加在尾部
while (len >= 3 && val[len - 3] < val[len - 1])
{
combine(len - 2);
}
}
while (len > 1)
combine(len - 1);
printf("%d\n", sum);
return 0;
}
View Code
石子合并-环形版
相比于直线版的，环形版可以从每一个点j开始，合并其后i堆石子为一堆，1 <= i <= n-1 ，合并的区间长度不受j的影响，而直线版的i满足: 1 <= i <= n - j ，合并的区间收到j的影响，那么我们就将整个环拆成n段链，求出合并这n段链中得分最大（小）者即可，其余操作和直线版一样
朴素写法
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>
#define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 1e7 + 7;
const ll mod = 1e9 + 7;
const int Max = 2e2 + 10;
int n;
int a[205];
int sum[205];
int dp1[205][205], dp2[205][205];
int main()
{
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i++)
{
if (i <= n)
scanf("%d", a + i), a[i + n] = a[i];
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j + i <= 2 * n; j++)
{
int e = i + j;
dp1[j][e] = inf;
dp2[j][e] = -1;
for (int k = j; k + 1 <= e; k++)
{
dp1[j][e] = min(dp1[j][e], dp1[j][k] + dp1[k + 1][e] + sum[e] - sum[j - 1]);
dp2[j][e] = max(dp2[j][e], dp2[j][k] + dp2[k + 1][e] + sum[e] - sum[j - 1]);
}
}
}
int min_val = inf, max_val = 0;
for (int i = 1; i <= n; i++)
{
min_val = min(min_val, dp1[i][i + n - 1]);
max_val = max(max_val, dp2[i][i + n - 1]);
}
printf("%d\n%d\n", min_val, max_val);
return 0;
}
View Code
四边形优化写法（目前只能求最小代价）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>
#define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 1e7 + 7;
const ll mod = 1e9 + 7;
const int Max = 1e3 + 10;
int n;
int a[Max<<1];
int sum[Max];
int dp[Max][Max],s[Max][Max];
int main()
{
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i++)
{
if (i <= n)
scanf("%d", a + i), a[i + n] = a[i];
sum[i] = sum[i - 1] + a[i];
s[i][i] = i;
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j + i <= 2 * n; j++)
{
int e = i + j;
dp[j][e] = inf;
for (int k = s[j][e-1]; k <= s[j+1][e]; k++)
{
if(dp[j][e] > dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1])
{
dp[j][e] = dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1];
s[j][e] = k;
}
}
}
}
int min_val = inf;
for (int i = 1; i <= n; i++)
{
min_val = min(min_val, dp[i][i + n - 1]);
}
printf("%d\n", min_val);
return 0;
}
View Code
内容总结
以上是互联网集市为您收集整理的石子合并（直线版+环形版）&（朴素写法+四边形优化+GarsiaWachs算法）全部内容，希望文章能够帮你解决石子合并（直线版+环形版）&（朴素写法+四边形优化+GarsiaWachs算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。