tyvj1014 - 乘法游戏 ——记忆化搜索DP

题目链接：https://www.tyvj.cn/Problem_Show.aspx?id=1014 f[i][j]表示区间［i，j］所得到的最小值。 不断地划分区间，把结果保存起来。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
long long int f[101][101];int a[101], i, j, n, INF=0x7f7f7f7f;
void dfs(int l, int r) {
    if(r-l<=1) {f[l][r]=0; return;} if(f[l][r]!=INF) return;
    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]);
}
int main(void) {
    freopen("in1.txt","r",stdin);
    scanf("%d",&n);for(i=1;i<=n;scanf("%d",a+i++))
        ;for(i=0;i<=n;++i)for(j=0;j<=n;++j)f[i][j]=INF;dfs(1,n);printf("%lld\n",f[1][n]);
    return 0;
}

=_=