【乘法游戏】

乘法游戏
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:8 测试通过:1

描述

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第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。

输入

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

输出

最小得分

样例输入

6
10 1 50 50 20 5

样例输出

3650

提示

http://www.tyvj.cn/Problem_Show.asp?id=1014

#include <iostream>
using namespace std;

#define MAXN 210

typedef unsigned long long int longint;

const longint INF = 1 << 31;

longint a[MAXN];

longint dp[MAXN][MAXN];

int n;

void iInit()
{
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
}

void iDynamicProgramming()
{
    for (int i = n - 2; i >= 1; i--)
    {
        for (int j = i + 2; j <= n; j++)
        {
            longint max = INF;
            for (int k = i + 1; k <= j - 1; k++)
            {
                if (max > dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
                {
                    max = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
                }
            }
            dp[i][j] = max;
        }
    }
}

void iShowResult()
{
    cout << dp[1][n] << endl;
}

int main()
{

    while (cin >> n)
    {
        iInit();

        iDynamicProgramming();

        iShowResult();

    }
    return 0;
}

// end
// ism