做网站要买数据库,北京网站建设认知,5 网站建设进度表,大学生做网站步骤设有N堆石子排成一排#xff0c;其编号为1#xff0c;2#xff0c;3#xff0c;…#xff0c;N。
每堆石子有一定的质量#xff0c;可以用一个整数来描述#xff0c;现在要将这N堆石子合并成为一堆。
每次只能合并相邻的两堆#xff0c;合并的代价为这两堆石子的质量…设有N堆石子排成一排其编号为123…N。
每堆石子有一定的质量可以用一个整数来描述现在要将这N堆石子合并成为一堆。
每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2 我们可以先合并1、2堆代价为4得到4 5 2 又合并 12堆代价为9得到9 2 再合并得到11总代价为491124
如果第二步是先合并23堆则代价为7得到4 7最后一次合并代价为11总代价为471122。
问题是找出一种合理的方法使总的代价最小输出最小代价。
输入格式 第一行一个数N表示石子的堆数N。
第二行N个数表示每堆石子的质量(均不超过1000)。
输出格式 输出一个整数表示最小代价。
数据范围 1≤N≤300
解题思路 dp[i][j]表示从第i堆石子到第j堆石子的最小花费。
代码如下
#include iostream
using namespace std;
const int INF 1 30;
const int N 300;
int n;
int s[N];int ans() {int dp[N][N];for (int i 1; i n; i)dp[i][i] 0;for (int len 1; len n; len)for (int i 1; i n - len; i) {int j i len;dp[i][j] INF;for (int k i; k j; k) {dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] s[j] - s[i - 1]);}}return dp[1][n];
}int main() {while (cin n) {s[0] 0;for (int i 1; i n; i) {int x;cin x;s[i] s[i - 1] x;}cout ans() endl;}return 0;
}
