39 lines
1,000 B
Text
39 lines
1,000 B
Text
fcn optim3(a){ // list --> (int,list)
|
|
aux:=fcn(n,k,a){ // (int,int,list) --> (int,int,int,list)
|
|
if(n==1){
|
|
p,q := a[k,2];
|
|
return(0,p,q,k);
|
|
}
|
|
if(n==2){
|
|
p,q,r := a[k,3];
|
|
return(p*q*r, p, r, T(k,k+1));
|
|
}
|
|
m,p,q,u := Void, a[k], a[k + n], Void;
|
|
foreach i in ([1..n-1]){
|
|
#if 0 // 0.70 sec for both tests
|
|
s1,p1,q1,u1 := self.fcn(i,k,a);
|
|
s2,p2,q2,u2 := self.fcn(n - i, k + i, a);
|
|
#else // 0.33 sec for both tests
|
|
s1,p1,q1,u1 := memoize(self.fcn, i,k,a);
|
|
s2,p2,q2,u2 := memoize(self.fcn, n - i, k + i, a);
|
|
#endif
|
|
_assert_(q1==p2);
|
|
s:=s1 + s2 + p1*q1*q2;
|
|
if((Void==m) or (s<m)) m,u = s,T(u1,u2);
|
|
}
|
|
return(m,p,q,u);
|
|
};
|
|
|
|
h=Dictionary(); // reset memoize
|
|
s,_,_,u := aux(a.len() - 1, 0,a);
|
|
return(s,u);
|
|
}
|
|
|
|
var h; // a Dictionary, set/reset in optim3()
|
|
fcn memoize(f,n,k,a){
|
|
key:="%d,%d".fmt(n,k); // Lists make crappy keys
|
|
if(r:=h.find(key)) return(r);
|
|
r:=f(n,k,a);
|
|
h[key]=r;
|
|
return(r);
|
|
}
|