POJ1651 Multiplication Puzzle

一、题目内容

【题目描述】

给你n张卡牌，每个卡牌有一个权值，当你取出一个卡片时，你会得到一个得分,例如10 1 50 20 5, 你拿出第二张，则会得到分数10 x 1 x 50，
要求拿完2 - n-1张卡牌，不能拿第一张和最后一张。例如拿的顺序是1，20，50， 则分数为10 x 1 x 50 + 50 x 20 x 5 + 10 x 50 x 5 = 8000。

【输入格式】

第一行一个数n。(3 < n < 100)
第二行n个整数代表权值。

【输出格式】

输出一个整数——最小的得分

【输入样例】

6
10 1 50 50 20 5

【输出样例】

3650

【测试网站】

poj1651

二、题目分析

区间DP,dp[i][j] 表示拿出i-j的牌的最小得分
dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + a[i-1] x a[k] x a[j+1]) (i<=k<=j)

三、代码示例

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;

int n,a[maxn];
long long dp[maxn][maxn] = {0};

int main()
{
  scanf("%d",&n);
  for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
  for(int i = n-1; i > 1; i--)
     for(int j = i; j < n; j++)
         {
           dp[i][j] = 1e18;
           for(int k = i; k <= j; k++)
             dp[i][j] = min(dp[i][j],dp[i][k-1] + dp[k+1][j] + a[i-1]*a[j+1]*a[k]);
          }
  printf("%d\n",dp[2][n-1]);
  return 0;
}