P1775 石子合并（弱化版） 题解

本文主要是介绍P1775 石子合并（弱化版） 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

分析

此题做法有好几种，其中一种是 dp，还有一种是记忆化搜索。

我们知道暴力 dfs 非常慢，但是加上记忆化优化后会原地起飞。

dfs(l,r)表示合并区间 $[l,r]$ 的最小价值，那么我们枚举 $[l,r]$ 间的一个中转点 $i$，答案就是：

1. 不合并；
2. 合并，加上代价；

取最小值。

dfs(l,r)=min(dfs(l,i)+dfs(i+1,r)+a[r]-a[l-1]);

$a$ 数组存的是前缀和，快速求合并 $[l,r]$ 的代价。

代码

#include <bits/stdc++.h>
using namespace std;int a[1005], f[1005][1005], n;int dfs(int l, int r) {if (l == r)return 0;//自己与自己合并，代价为0if (f[l][r] != INT_MAX)return f[l][r];//记忆化，已经求解的直接返回for (int i = l; i < r; ++i) {f[l][r] = min(f[l][r], dfs(l, i) + dfs(i + 1, r) + a[r] - a[l - 1]);}return f[l][r];
}int main() {cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {f[i][j] = INT_MAX;}}for (int i = 1; i <= n; i++)cin >> a[i], a[i] += a[i - 1];cout << dfs(1, n);return 0;
}

区间动归 dfs 模板

最后，安利一个区间合并的 dfs 模板。其实就是上面复制下来的~

int dfs(int l, int r) {if (l == r)return 0;if (f[l][r] != INT_MAX)return f[l][r];for (int i = l; i < r; ++i) {f[l][r] = min(f[l][r], dfs(l, i) + dfs(i + 1, r) + a[r] - a[l - 1]);}return f[l][r];
}

这篇关于P1775 石子合并（弱化版） 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---