首页 > 编程语言 > 详细

石子合并问题 & GarsiaWachs算法

时间:2021-02-16 23:26:22      阅读:25      评论:0      收藏:0      [点我收藏+]

引入

在一个操场上摆放着一排 \(N\) 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 \(2\) 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。
试设计一个算法,计算出将 \(N\) 堆石子合并成一堆的最小得分。
数据范围 \(n \le 4e4\)

一个较为朴素的算法

不是暴力

按照区间DP的思路来做

\(f_{i, j}\) 表示区间 \([i, j]\) 合并的最小得分,枚举一个端点 \(k\),那么有转移方程:(其中 \(a\) 数组是预处理后的前缀和)

\[f_{i, j} = \min \{ f_{i, j}, f_{i, k} + f_{k + 1, j} + a_j - a_{i - 1} \} \]

注意 \(i\) 要倒序枚举,\(j\) 要正序枚举

答案就是 \(f_{1, n}\)

时间复杂度: \(O(n^3)\);空间复杂度:\(O(n^2)\)

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 22335;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n;
int a[MAXN];
int f[MAXN][MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == ‘-‘), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - ‘0‘ , ch = getchar();
    return f ? -s : s;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read() + a[i - 1];
    for(int i = n; i >= 1; --i){
	for(int j = i; j <= n; ++j){
            if(i == j) continue;
	    f[i][j] = INF;
	    for(int k = i; k < j; ++k) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
	}
    }
    printf("%d\n", f[1][n]);
    return 0;
}

GarsiaWachs算法

发现数据范围太大了,上面的算法已经不能满足我们的需求,这里有一种优化算法,专门用来解决石子问题

每次操作,从前向后找一个最小的 \(k\),使其满足 \(a_{k - 1} \le a_{k + 1}\),然后合并 \(a_{k - 1}\)\(a_k\)
\(k\) 开始向前找到第一个 \(j\) 使得 \(a_j > a_{k - 1} + a_k\),并将合并后的新值插入位置 \(j\) 后面
进行 \(n - 1\) 次结束,在合并过程中统计答案即可

时间复杂度:\(O(n^2)\);空间复杂度:\(O(n)\)

正确性证明:作为一个OI,会应用就好啦,其实是我不会

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

LL n, ans = 0;
vector<int> a;

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == ‘-‘), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - ‘0‘ , ch = getchar();
    return f ? -s : s;
}

int merge(){//GarsiaWachs算法
    int k = a.size() - 2;
    for(int i = 0; i < a.size() - 2; ++i)
    	if(a[i] <= a[i + 2]){
 k = i; break;
 }
    int sum = a[k] + a[k + 1];
    a.erase(a.begin() + k);
    a.erase(a.begin() + k);
    int inst = -1;
    for(int i = k - 1; i >= 0; --i)
    	if(a[i] > sum){
 inst = i; break;
 }
    a.insert(a.begin() + inst + 1, sum);
    return sum;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) a.push_back(read());
    for(int i = 1; i < n; ++i) ans += merge();
    printf("%lld", ans);
    return 0;
}

石子合并问题 & GarsiaWachs算法

原文:https://www.cnblogs.com/Silymtics/p/14407370.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!