tyvj1014

题目链接：https://www.tyvj.cn/Problem_Show.aspx?id=1014

f[i][j]表示区间［i，j］所得到的最小值。

不断地划分区间，把结果保存起来。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <algorithm>
 4 using namespace std;
 5 long long int f[101][101];int a[101], i, j, n, INF=0x7f7f7f7f;
 6 void dfs(int l, int r) {
 7     if(r-l<=1) {f[l][r]=0; return;} if(f[l][r]!=INF) return;
 8     for(int i=l+1;i<=r-1;++i) dfs(1,i),dfs(i,r),f[l][r]=min(f[l][r],f[l][i]+f[i][r]+a[i]*a[l]*a[r]);
 9 }
10 int main(void) {
11     freopen("in1.txt","r",stdin);
12     scanf("%d",&n);for(i=1;i<=n;scanf("%d",a+i++))
13         ;for(i=0;i<=n;++i)for(j=0;j<=n;++j)f[i][j]=INF;dfs(1,n);printf("%lld
",f[1][n]);
14     return 0;
15 }

=_=