codevs 1966 乘法游戏

1966 乘法游戏

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题目描述 Description

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两张牌。
　　你的目标是使得分的和最小。
　　例如，如果数是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。

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

6
10 1 50 50 20 5

样例输出 Sample Output

3650

数据范围及提示 Data Size & Hint

代码：

/* 错误原因 :这个DP方程说明，每次取数只能取一个区间的数，而题目没有这个要求

        for(int i=n-2;i>=2;--i)

      for(int j=i+1;j<=n-1;++j)

      f[i][j]=min(min(f[i][j],f[i+1][j]+a[i]*a[i-1]*a[j+1]),f[i][j-1]+a[i-1]*a[j]*a[j+1]);*/

/*正确解答：f[i][j]表示合并i--j这个区间不包括i和j的最小数

f[i][j]=min(f[i][j],f[i][k]+f[k][j]+num[i]*num[j]*num[k]);因为取数可以跳着取，那么就要再加一重循环，循环这个区间内所有的取数可能*/

/*这个题目是区间型DP，而不是序列性DP*/

#include<cstdio>

#include<iostream>

using namespace std;

#define N 101

#include<cstring>

int f[N][N],n;

int num[N];

void input()

{

    scanf("%d",&n);

    for(int i=;i<=n;++i)

    scanf("%d",&num[i]);

    memset(f,,sizeof(f));

    for(int i=;i<=n;++i)

    f[i][i+]=;/*注意这个初始化，合并两个数的区间，不行的*/

}

void dp()

{

    for(int i=n-;i>=;--i)

      for(int j=i+;j<=n;++j)

        for(int k=i+;k<=j-;++k)

        f[i][j]=min(f[i][j],f[i][k]+f[k][j]+num[i]*num[j]*num[k]);

}

int main()

{

    input();

    dp();

    cout<<f[][n]<<endl;

    return ;

}