石子合并
石子合并是一类动态规划问题，其中石子合并代价的解释为两堆石子的数量和。分为如下典型的三类：
不加限制的合并
即为每次任意合并两堆，输出为最小花费。
贪心策略每次找出最小的两个元素即可（n-1轮）：
1
2
3
4
5
6
7
| n=int(input())
w=list(map(int, input().split()))
for i in range(n-1):
label_min=min(w)
w.remove(label_min)
w[w.index(min(w))]+=label_min
print(w[0])
|
线性（相邻）合并
即为每次合并相邻两堆，输出为最小花费。
动态规划，具体思路为：
- 确定状态：设dp[i][j]表示合并第i到j个石子的最小代价。
- 确定状态转移方程：对于第i到第j个石子的合并，可以选择在任意一个位置k断开，将问题分成合并i到k之间的石子和合并k+1到j之间的石子两个子问题。因此，可以得到状态转移方程：
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j]-sum[i-1]) (i<=k<j)
其中sum[i]表示第i个石子前（包括i）的重量和，即需要合并的代价。
- 确定边界：当只有一个石子时，代价为0，因此dp[i][i] = 0。
- 最终结果：最终的结果为dp[1][n]，表示合并全部石子的最小代价。
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
| #include <iostream>
using namespace std;
int f[310][310];
int main() {
int n;
cin >> n;
int w[n+1], sum[n+1];
sum[0]=0;
for(int i=1;i<=n;i++){
cin>>w[i];
sum[i]=sum[i-1]+w[i];
}
for(int l=2;l<=n;l++){
for(int i=1;i+l-1<=n;i++){
int j=i+l-1;
f[i][j]=1e8;
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j], f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
}
}
cout<<f[1][n]<<endl;
return 0;
}
|
环形合并
将环形转换为直线：通过将石子数量变为2n来转换成直线问题。 即将两个数组w[1,…,n]串联即可，这样存在1~n ; 2~n~1 ; n~1~n-1共n个数组，对于n个数组，采用线性合并的方法即可。
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
| #include<iostream>
using namespace std;
const int N=410;
int f[N][N];
int g[N][N];
int main(){
int n;
cin>>n;
int w[n+1];
int sum[2*n+1]={0};
for(int i=1;i<=n;i++){
cin>>w[i];
sum[i]=sum[i-1]+w[i];
}
for(int i=1;i<=n;i++){
sum[i+n]=sum[i-1+n]+w[i];
}
for(int l=2;l<=2*n;l++){
for(int i=1;i+l-1<=2*n;i++){
int j=i+l-1;
f[i][j]=1e8;
g[i][j]=0;
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j], f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
g[i][j]=max(g[i][j], g[i][k]+g[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int label1=f[1][n];
int label2=g[1][n];
for(int i=2;i<=n;i++){
if(f[i][i+n-1]<label1)label1=f[i][i+n-1];
if(g[i][i+n-1]>label2)label2=g[i][i+n-1];
}
cout<<label1<<endl;
cout<<label2<<endl;
return 0;
}
|
