10147. 「一本通 5.1 例 1」石子合并

题意

将 $n$ 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 $n$ 及每堆的石子数,并进行如下计算:
  1. 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最大。
  2. 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最小。

思路

DP水过去。。。

求最大值

设$f[i][j]$表示区间$[i,j]$得分的最大值。 很容易可以想到:
$$f[i][j]=max(f[i][k]+f[k+1][j]+dist(i,j)))$$ $$dist(i,j)=a[i]+a[i+1]+…+a[j-1]+a[j]$$ 所以我们设$sum[i]=a[1]+a[2]+…+a[i-1]+a[i]$ 可得:
$$sum[i]=sum[i-1]+a[i]$$
那么:
$$f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])$$
但是,仔细读题,发现是环。。。! 所以我们将环转换成链,即将$a$数组往后$n$个单位复制一遍。

最小值

与最大值差不多。改一个符号$max——>min$。
暂无评论

发送评论


				
上一篇
下一篇