提交的人好多。。。。

AC100！！

郁闷 一开始上界定义小了... 第二次提交还忘了 把注释掉的freopen改回来，，，，，感觉自己弱爆了.....

f[i,j]表示从第 i 堆到第 j 堆合并的最小值，
st[i]表示从1到 i 石头的花费
用len表示当前长度
f[i,j]初始为maxlongint
状态转移方程 ：[b][color=red]f[i,j]=min{f[i,j],f[i,k]+f[k+1,j]+st[j]-st[i-1]}（k<>j)

MK

寒假以来第一份有效率的DP= =纪念一下

回复 @CSY.Girl_Queen :
对于一个问题而言，存在某种贪心策略可得到局部最优解。
但是若证明该贪心策略所得到的局部最优解亦是全局最优解仍需严格的证明过程。
在这里，我误认为三集合就可以表示所有的状态，但是存在以下问题：
1。集合$ABC$都代表着在全局中始终为最优解的集合。却无法确定集合的合并方式。
2.无法确定先选取哪个集合为B进行合并$(A(BCD)),((ABC)D)$

回复 @CH.Genius_King :
我将反例用统一的形式表示，可表示为4种状态的情况。
设状态集合$A,B,C,D$，形式可以包含多种决策，但他们在形式上是统一的。
形式1双双合并再合并
$F(ABCD)=W(A)+W(B)+W(C)+W(D)+W(AB)+W(CD)$
形式2逐次相邻合并型
$F(ABCD)=W(A)+W(B)+W(AB)+W(C)+W(ABC)+W(D)$
形式1$δ(ABCD)=W(D)$
形式2$δ(ABCD)=W(AB)$

然后我就无意间又证明贪心算法是对的！

我们都知道这是一道很基础的DP。
$F$为所需求的状态值，在石子归并问题中理解为权重。$W$为物品重量，$φ$为与参数(状态$K$)相关的状态转移权重。
$F(A)=Min(F(A-K)+φ(K))$类型的动归(A,K表状态集合，在石子归并问题中我们使它内部元素有序)。
在石子归并问题中，我们认为$φ(K)=W(A)+W(A-K)$
可是，如何证明它不可以使用贪心算法呢？
假设有序集合$A,B,C$表示不同的状态。终止状态为$(ABC)$初始价值(状态)则为$Ω(INIT)=F(A)+F(B)+F(C)$
策略1$F(ABC)=W(A)+W(B)+W(AB)+W(ABC)+Ω(INIT)$
策略2$F(ABC)=W(B)+W(C)+W(BC)+W(ABC)+Ω(INIT)$
两式比较取差异部分：
策略1$δ(ABC)=2W(A)$
策略2$δ(ABC)=2W(C)$
此时的可以看出在初末状态相同时，策略1与策略2有明显的优劣。我们只需修改$ABC$集合代表的状态（只需保证其始终为有序态即可），既可以得到全局最优解

回复 @ch3coooh :
这来自于tyvj，本来是“傻子”的

对啊沙子不可数。。。

石子归并为毛说是沙子。。。。。。。
世界观秒崩

io输出没去掉居然没判错= =.............

不用输出合并过程，并且是线性排列而非环状排列，这题简直弱爆了。难怪难度只有一星

不用输出合并过程，并且是线性排列而非环状排列，这题简直弱爆了。难怪难度只有一星

我的代碼很詳細。

還是有點不懂。

边界很重要。