题目描述
你有n个数, 要将n个数并成1个. 只有相邻两个数才能合并, 花费两个数的和(如合并a, b, 花费a + b) 求最小花费
解法
先来组数据 --- 1 2 3 4 5
首先, 你可以假设你有两个机器人, 他们会告诉你把一堆东西合并好的花费
那么你可以让他们这样做
1号: 求合并 1 2 3 的最小花费
2号: 求合并 4 5 的最小花费 --> 9
然后1号机器人会召唤3号和4号机器人:
3号:求合并 1 2 的最小花费 --> 3
4号:求 3 的最小花费 --> 0
然后此时1号机器人就知道了1 2 3 的花费(一种解):
1 + 2 + 3 + 3 = 9
BUT WHY?
1 2 3要合并, 首先要加上每次合并的花费即+3
同时当并得只有两个数时, 比如 3 3, 那么合并要 3 + 3,
其实就是 1 + 2 + 3
学废了吗
当然, 一号机器人也可这样分: 1 和 2 3, 求其花费, 然后取最小值
你也是如此: 分成 1 2 3 4 和 5 或 1 2 和 3 4 5 or ......, 然后取最小值
然后就是伟大的AC CODE
代码
记忆化:
#include <bits/stdc++.h>
using namespace std;
int n, a[85], sum[85];
int mem[100][100];
int dfs(int l, int r) {
if (mem[l][r] != -1)//记忆化代码,有的直接输出
return mem[l][r];
if (l == r)//一个数时
return mem[l][r] = 0;
int ans = 1e9;//记得开大一点哦
for (int k = l; k < r; k++) { // k 代表 分成1~k, k+1~n
int tmp = dfs(l, k) + dfs(k + 1, r) + sum[r] - sum[l - 1];
ans = min(ans, tmp);
}
return mem[l][r] = ans;//没有的先求
}
int main() {
memset(mem, -1, sizeof(mem));//归零
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];//这是前缀和
}
cout << dfs(1, n);//求合并1到n的最小花费
return 0;
}
DP
#include <bits/stdc++.h>
using namespace std;
const long long N = 3e3, MOD = 998244353;
long long n, dp[105][105], a[105], sum[105];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = INT_MAX / 2;//初始化
}
dp[i][i] = 0;
}
for (int i = 1; i <= n; i++) {//需要注意的是DP的顺序,要先枚举长度
for (int st = 1; st <= n; st++) {
int en = st + i - 1;
for (int p = st; p < en; p++) {
if (st != en)
dp[st][en] = min(dp[st][p] + dp[p + 1][en] + sum[en] - sum[st - 1], dp[st][en]);
}
}
}
cout << dp[1][n];
return 0;
}
共 3 条回复
哦好像也可以
好的~不过不是"```cpp"吗
建议高亮：
~ ~ ~c p p
（中间插入代码）
~ ~ ~
实际上~之间是没有空格的（为了写给你看）