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$。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇