POJ 1651 Multiplication Puzzle(区间DP)

Problem Description

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring

10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be

1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

 Input

The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.

 Output

Output must contain a single integer - the minimal score.

 Sample Input

6

10  1  50  50  20  5

 Sample Output

3650

题意：

给出一个长度为n的序列，删除一些数，每次删除一个数a【i】要付出a【i-1】* a【i】 * a【i+1】的代价，问要删除到只剩左右两个元素最少需要付出多少代价。

思路：

区间DP，L和R表示在区间L到R内，除了左边界L和右边界R不删除，删除中间所有元素所需要的最小代价。
DP【i】【j】即表示区间边界。其中两两相邻的数中间没有数可删，即该区间内花费初始化为0。这样从最小区间长度2开始，统计3个数存在时的最小花费。这样平移这段区间，求出所有该长度的花费，求得小区间后即可求更大的区间，这样不断递推下去。最终得到区间长度为n的整个序列的最小花费。注意结果可能超int。

代码：

#include<stdio.h>///区间DP
#include<algorithm>
#include<string.h>
#define LL long long
using namespace std;
const int maxn=108;
int n;
LL a[maxn],dp[maxn][maxn];///DP[i][j]表示区间的左右边界，表示删除左右边界之间的数所要的花费
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof dp);
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        for(int i=2; i<=n; i++)
            for(int j=1; j+i<=n; j++)
            {
                dp[j][j+i]=1e12;
                for(int k=j+1; k<j+i; k++)///在一个区间内选择一个k值，这个k值和左右边界相乘，意思是删除k，并且从边界到k这两段区间优先被删掉，求和后取一个花费最小值
                    dp[j][j+i]=min(dp[j][j+i],a[j]*a[k]*a[j+i]+dp[j][k]+dp[k][j+i]);
//                printf("dp[%d][%d] = %lld\n",j,j+i,dp[j][j+i]);
            }
        printf("%lld\n",dp[1][n]);///最后因为只留下第一个值和最后一个值，因此这段区间内所有值被删去的最优解即answer
    }
   return 0;
}

作者：kuronekonano
转载原文：https://blog.csdn.net/kuronekonano/article/details/80077503