【题目描述】

桌子上从左到右放着n张牌，每张牌上都有一个正整数。每次，我们可以从中拿出一张牌（不能拿第一张和最后一张牌），得分就是这张牌的数乘以他左边和右边的数。如此不断的重复，最后就只剩下两张牌了。现在，你的目标就是使得分的和最小。

    例如，如果数是10 1 50 20 5，依次拿1、20、50，总分是                       10*1*50+50*20*5+10*50*5=8000，而拿50、20、1，总分是1*50*20+1*20*5+10*1*5=1150。 

【输入格式】

输入文件的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。

【输出格式】

输出文件只有一个数字：最小得分

【分析】

区间dp，状态：f[i][j]表示[i,j]区间内的最小分数。

我们在区间内枚举一个k，表示取的那个数，就可以解出f[i][j]=min(f[i][k]+a[i]*a[k]*a[j]+f[k][j])

答案就是f[1][n]，初始值，所有的都是inf，f[i][i]=0,f[i-1][i]=0,f[i][i+1]=0。

【代码】

1 #include
     
       2  3 using namespace std; 4 const int inf=9999999; 5 int f[110][110],n,a[110]; 6 int main() 7 { 8     memset(f,inf,sizeof(f)); 9     scanf("%d",&n);10     for(int i=1;i<=n;i++){11         scanf("%d",&a[i]);12         f[i-1][i]=0,f[i][i]=0,f[i][i+1]=0;13     }14     for(int i=2;i<=n-2;i++) f[i-1][i+1]=a[i-1]*a[i]*a[i+1];15     for(int i=n-2;i>=1;i--){16         for(int j=i+2;j<=n;j++){17             for(int k=i+1;k