切换到宽版
  • 4888阅读
  • 2回复

动态规划高手进 [复制链接]

上一主题 下一主题
离线独孤幽梦
 
只看楼主 倒序阅读 0 发表于: 2007-11-05
第三,四题
描述:初中奥赛模拟练习试卷1.doc
附件: 初中奥赛模拟练习试卷1.doc (47 K) 下载次数:61
离线fchqq
只看该作者 1 发表于: 2007-11-06
1、f[I,j]表示第i个矩阵到第j个矩阵连乘的最少次数。
2、a.x a.y表示第i个矩阵的行号和列号
3、转移方程:
F[I,j]=min{F[I,k]+f[k+1,j]+ai.x*ai.y*aj.y}


首先是两两相乘
For i:=1 to n-1 do
                F[i,i+1]:=a.x*a.y*a[i+1].y;
然后是更大规模的连乘
For len:=3 to n do
    For i:=1 to n-len+1 do
Begin
  j:=i+len-1;F[i,j]:=maxlongint;
For k:=i to j-1 do
  If F[i,j]>F[i,k]+F[k+1,j]+a.x*a[k].y*a[j].y Then 
  Begin
      F[i,j]:=F[i,k]+F[k+1,j]+a.x*a[k].y*a[j].y;
  End;
End ;
离线独孤幽梦
只看该作者 2 发表于: 2007-11-10
谢谢
快速回复
限100 字节
 
上一个 下一个