pascal （区间dp）经典的区间动归,一排石子（一排不是一圈,不要想复杂了）,每次可以合并相邻两堆,耗费体力为两堆石子质量和,求最小耗费体力.我写的转移方程是f[i,j]=f[i,k]+f[k+1,j]+t(i,j);t是求
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/20 06:40:45
pascal （区间dp）经典的区间动归,一排石子（一排不是一圈,不要想复杂了）,每次可以合并相邻两堆,耗费体力为两堆石子质量和,求最小耗费体力.我写的转移方程是f[i,j]=f[i,k]+f[k+1,j]+t(i,j);t是求
pascal （区间dp）
经典的区间动归,一排石子（一排不是一圈,不要想复杂了）,每次可以合并相邻两堆,耗费体力为两堆石子质量和,求最小耗费体力.
我写的转移方程是
f[i,j]=f[i,k]+f[k+1,j]+t(i,j);
t是求i到j的石子总数,f[i,j]求的是求第i堆到等j堆的石子和的总数
我的问题是上面的循环要怎么写啊?
pascal （区间dp）经典的区间动归,一排石子（一排不是一圈,不要想复杂了）,每次可以合并相邻两堆,耗费体力为两堆石子质量和,求最小耗费体力.我写的转移方程是f[i,j]=f[i,k]+f[k+1,j]+t(i,j);t是求
总体思想就是列出所有可能.
procedure work;
begin
for i:=1 to n do
f[i,i]:=0;
for p:=1 to n-1 do
for i:=1 to n-p do
begin
j:=i+p;
f[i,j]:=maxlongint;
for k:=i to j-1 do
if f[i,j]>f[i,k]+f[k+1,j]
then f[i,j]:=f[i,k]+f[k+1,j];
f[i,j]:=f[i,j]+a[j]+a[i-1];
//每次循环将下一个f[i,j]入队列
end;
end;
过程就是这样的.a[]存的是i-1到i的数量,简单来说就是初始化.