本文主要是介绍AcWing 282. 石子合并,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
必看的视频讲解↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
【E28【模板】区间DP 石子合并——信息学竞赛算法】
合并过程总开销等于红色数字总和,可以理解为花费的总体力!
f数组的含义是f【i】【j】是从第i
堆石子开始到第j
堆石子的花费体力最小值
如何理解三层for呢?
第一层for是控制区间长度len
,第二层for是控制区间起点位置i
,第三层for是控制区间内的分割点的位置k
注意len必须从2开始!
s数组刚开始存储每堆石子的质量,后面用于存储前缀和
,方便快速求取区间和
的问题!
时间复杂度 O ( n 3 ) O(n^3) O(n3)
#include<iostream>
#include<algorithm>
#define N 310
using namespace std;
int n;
int f[N][N] , s[N];
int main(){cin >> n;for(int i = 1 ; i <= n ; ++ i) cin >> s[i] , s[i] += s[i - 1];for(int len = 2; len <= n; ++ len){for(int i = 1; i + len - 1 <= n; ++ i){int l = i , r = l + len - 1;f[l][r]=1e9;for(int k = l ; k < r ; ++ k){f[l][r] = min(f[l][r] , f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);}}}cout << f[1][n];return 0;
}
这篇关于AcWing 282. 石子合并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!