作业帮pascal （区间dp）经典的区间动归,一排石子（一排不是一圈,不要想复杂了）,每次可以合并相邻两堆,耗费体力为两堆石子质量和,求最小耗费体力.我写的转移方程是f[i,j]=f[i,k]+f[k+1,j]+t(i,j);t是求
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 04:59:57
![pascal （区间dp）经典的区间动归,一排石子（一排不是一圈,不要想复杂了）,每次可以合并相邻两堆,耗费体力为两堆石子质量和,求最小耗费体力.我写的转移方程是f[i,j]=f[i,k]+f[k+1,j]+t(i,j);t是求](/uploads/image/z/15257128-40-8.jpg?t=pascal+%EF%BC%88%E5%8C%BA%E9%97%B4dp%EF%BC%89%E7%BB%8F%E5%85%B8%E7%9A%84%E5%8C%BA%E9%97%B4%E5%8A%A8%E5%BD%92%2C%E4%B8%80%E6%8E%92%E7%9F%B3%E5%AD%90%EF%BC%88%E4%B8%80%E6%8E%92%E4%B8%8D%E6%98%AF%E4%B8%80%E5%9C%88%2C%E4%B8%8D%E8%A6%81%E6%83%B3%E5%A4%8D%E6%9D%82%E4%BA%86%EF%BC%89%2C%E6%AF%8F%E6%AC%A1%E5%8F%AF%E4%BB%A5%E5%90%88%E5%B9%B6%E7%9B%B8%E9%82%BB%E4%B8%A4%E5%A0%86%2C%E8%80%97%E8%B4%B9%E4%BD%93%E5%8A%9B%E4%B8%BA%E4%B8%A4%E5%A0%86%E7%9F%B3%E5%AD%90%E8%B4%A8%E9%87%8F%E5%92%8C%2C%E6%B1%82%E6%9C%80%E5%B0%8F%E8%80%97%E8%B4%B9%E4%BD%93%E5%8A%9B.%E6%88%91%E5%86%99%E7%9A%84%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B%E6%98%AFf%5Bi%2Cj%5D%3Df%5Bi%2Ck%5D%2Bf%5Bk%2B1%2Cj%5D%2Bt%28i%2Cj%29%3Bt%E6%98%AF%E6%B1%82)
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的数量,简单来说就是初始化.