POJ 1651 Multiplication Puzzle （区间DP，经典）

题意：

　　给出一个序列，共n个正整数，要求将区间[2,n-1]全部删去，只剩下a[1]和a[n]，也就是一共需要删除n-2个数字，但是每次只能删除一个数字，且会获得该数字与其旁边两个数字的积的分数，问最少可以获得多少分数？

思路：

　　类似于矩阵连乘的问题，用区间DP来做。

　　假设已知区间[i,k-1]和[k+1,j]各自完成删除所获得的最少分数，那么a[k]是区间a[i,j]内唯一剩下的一个数，那么删除该数字就会获得a[k]*a[i-1]*a[i+1]的分数了。在枚举k的时候要保证[i,j]的任一子区间都已经完成了计算。

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f7f7f7f
#define LL unsigned long long
using namespace std;
const double PI  = acos(-1.0);
const int N=110;

int a[N];
LL dp[N][N];

int cal(int n)
{
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; i++)
    for(int j=i; j<=n; j++)
        dp[i][j]=INF;

    for(int j=2; j<n; j++)
    for(int i=j; i>1; i--)
    for(int k=i; k<=j; k++)     //枚举区间a[i->j]最后剩下的数字是a[k]
        dp[i][j]=min(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[k]*a[i-1]*a[j+1]);

    return dp[2][n-1];
}


int main()
{
    freopen("input.txt", "r", stdin);
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)    scanf("%d",&a[i]);
        printf("%d
", cal(n));
    }
    return 0;

}