先上题目：
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6162 | Accepted: 3758 |
Description
Input
Output
Sample Input
6 10 1 50 50 20 5
Sample Output
3650
题意：给出一串数字，然后给你一种操作，选择非边缘的那两个数字的数字，然后获得值为这个数字与其左右两个数一共三个数的乘积的得分，然后被选的那个数消失，问最终只剩下两个数的时候总得分什么时候最大。
这一题是区间DP,我们可以枚举某一个数，然后求如果最终是这个数消失的话能得到的最大得分是多少就可以了。
状态转移方程：dp[i][j][k]=max(dp[i][j][k],(i+1~j-1的最值) + (j+1~k-1的最值) +i*j*k)
这里使用dfs来求值比较方便，而且递归的深度不会很长，所以不用担心爆栈或者时间的问题。
这里使用递归的方法实现的另一个原因的因为我平时写DP比较习惯用递推的形式，但是只掌握一种实现方式还是不够，毕竟不同的情况用不同的实现方式会有不一样的效果。
上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define MAX 102 6 #define LL long long 7 using namespace std; 8 9 const int limit = 100000002; 10 int p[MAX]; 11 int dp[MAX][MAX][MAX]; 12 int n; 13 14 int dfs(int a,int b,int c){ 15 int minn=limit; 16 if(dp[a][b][c]!=-1) return dp[a][b][c]; 17 dp[a][b][c]=p[a]*p[b]*p[c]; 18 for(int i=a+1;i<b;i++){ 19 dfs(a,i,b); 20 minn = min(minn,dp[a][i][b]); 21 } 22 if(a+1<b) dp[a][b][c]+=minn; 23 minn = limit; 24 for(int i=b+1;i<c;i++){ 25 dfs(b,i,c); 26 minn = min(minn,dp[b][i][c]); 27 } 28 if(b+1<c) dp[a][b][c]+=minn; 29 return dp[a][b][c]; 30 } 31 32 int main() 33 { 34 int sum; 35 //freopen("data.txt","r",stdin); 36 while(~scanf("%d",&n)){ 37 for(int i=1;i<=n;i++) scanf("%d",&p[i]); 38 memset(dp,-1,sizeof(dp)); 39 sum=limit; 40 for(int i=2;i<n;i++){ 41 dfs(1,i,n); 42 sum = min(sum,dp[1][i][n]); 43 } 44 printf("%d\n",sum); 45 } 46 return 0; 47 }
POJ - 1651 - Multiplication Puzzle,布布扣,bubuko.com
POJ - 1651 - Multiplication Puzzle
原文：http://www.cnblogs.com/sineatos/p/3846449.html
