poj1651 Multiplication Puzzle--区间dp

原题链接：​​http://poj.org/problem?id=1651​​

题意：给出N个数，每次从中抽出一个数(第一和最后一个不能抽)，每次的得分为抽出的数与相邻两个数的乘积，直到只剩下首尾两个数为止，问最小得分是多少

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

int n;
int v[105];
int dp[105][105];//注意这里的i和j表示的是开区间，也就是i和j里边的数取完的最小值，i和j不包括

int main()
{
  while (~scanf("%d", &n))
  {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        dp[i][j] = INF;

    for (int i = 1; i <= n; i++)
      scanf("%d", &v[i]);

    for (int i = 1; i <= n; i++)
      dp[i][i] = dp[i][i + 1] = 0;

    for (int l = 1; l <= n; l++)
    {
      for (int i = 1; i + l <= n; i++)
      {
        int j = i + l;
        for (int k = i; k <= j; k++)
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]);
      }
    }

    printf("%d\n", dp[1][n]);
  }

  return 0;
}