POJ 1651 Multiplication Puzzle(区间DP)

题目大意：
给你n个数，可以取[2,n-1]的数，若取a[i]则花费是a[i]与和a[i]相邻两数的乘积，比如有5个数字10 1 50 20 5，
玩家可以依次拿走1、20、50，总花费10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000。
依次拿走50、20、1，总花费1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150。
求最小的总花费。
解题思路：
dp[i][j]表示取完[i+1,j-1]内的数的最小花费。
于是得到状态转移方程：dp[i][j]=min(dp[i][j],dp[i][k+1]+dp[k+1][j]+a[i]*a[k+1]*a[j]),(i<k+1<j)
还是菜啊，之前想的状态转移方程是dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j])差一点。。。

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int N=205;
 8 const LL INF=1e18;
 9 LL a[N],dp[N][N];
10 
11 int main(){
12     int n;
13     while(cin>>n){
14         for(int i=1;i<=n;i++){
15             cin>>a[i];
16         }
17         for(int len=2;len<n;len++){
18             for(int i=1;i+len<=n;i++){
19                 int j=i+len;
20                 dp[i][j]=INF;
21                 //枚举删除[i+1,j-1]内的数
22                 for(int k=i;k<j-1;k++){
23                     dp[i][j]=min(dp[i][j],dp[i][k+1]+dp[k+1][j]+a[i]*a[k+1]*a[j]);
24                 }
25             }
26         }
27         cout<<dp[1][n]<<endl;
28     }
29     return 0;
30 }