问题描述1
在一个直线上放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分。 测试用例： 4（石子的堆数） 4 4 5 9（每一堆的石子数目） 输出： 43
解题思路1
- 如果只有一堆石子，不需要合并，费用为0。
- 如果有两堆石子，需要一次合并，费用就是两堆石子之和。
- 如果有三堆，则需要两次合并，费用就是第1堆与第二堆合并以及第2堆和第3堆合并费用的较小值，加上三堆石子数量总和。
- 推广到n堆石子的情况，需要n-1次合并，把这些石子分为第1到第k堆，和第k+1到第n堆，k从1取值到n-1，两部分分别求合并费用，k取使两部分的合并费用总和最小的值，最后再加上所有石子的数量和，即为最小合并费用
- 经过以上分析，我们得出了状态转移方程； \[dp[i][j]=dp[i][k]+dp[k+1][j]+sum[i][j]\] 其中 dp[i][j]表示将第i堆至第j堆的石子合并，sum[i][j]表示第i堆至第j堆石子数量总和。 其中i，j分别表示第几堆石子： 当j-i=0，只有一堆石子，花费为0。 当j-i=1，两堆石子。 当j-i=n，有n+1堆石子。 所以，在计算费用时，最外层用j-i来控制循环，数据是斜着一行一行求出。
C++代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
int dp[1005][1005];
int a[1005];
int main()
{
int n;
cout << "请输入石子堆数：" << endl;
cin >> n;
cout << "请输入每堆石子数：" << endl;
for (int i = 0;i < n;i++)
{
cin >> a[i];
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n - i; j++)
{
int jj = j + i;
int min = INF;
int s = 0;
for (int k = j; k < jj; k++)
{
s += a[k];
int t = dp[j][k] + dp[k + 1][jj];
if (t < min)
{
min = t;
}
}
s += a[jj];
dp[j][jj] = min + s;
}
}
cout << "最小得分：" << endl;
cout << dp[0][n - 1];
return 0;
}
|
问题描述2
长江俱乐部在长江设置了n个游艇出租站1,2,…n，游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j)，设计一个算法，计算出从出租站1到出租站n所需要的最少租金。 测试用例： 3（站数） 5 15（第一站到其他相应各站的租金） 7（第二站到其他相应各站的租金） 输出： 12
解题思路2
假设p[i][j]表示从i点出发，到j点租船的最小费用，则 p[i][j+1]=min{p[i][j],m[i][j+1]} 其中m[i][j]为输入的数据，表示第i个租船点到j个还船点的直接费用，我们可以通过比较两个值的大小来得到最小费用。最终的结果就是 p[0][n-1]
C++代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<iostream>
using namespace std;
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
int n;
cout << "请输入站点数：" << endl;
cin >> n;
int** m = new int* [n];
for (int i = 0; i < n; i++) {
m[i] = new int[n];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
m[i][j] = 0;
}
}
cout << "按顺序输入站点到其他站点的租金（站点的租金以空格间隔，下一个站点以回车输入）：" << endl;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cin >> m[i][j];
}
}
int** p = new int* [n];
for (int i = 0; i < n; i++) {
p[i] = new int[n];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
int minNum = m[0][i];
for (int j = 0; j < i; j++) {
minNum = min(minNum, p[0][j] + m[j][i]);
}
p[0][i] = minNum;
}
cout<<"最小花费是：" << endl;
cout << p[0][n - 1];
}
|