poj 1651 Multiplication Puzzle（区间DP，直接用矩阵相乘的方式也对）

本文主要是介绍poj 1651 Multiplication Puzzle（区间DP，直接用矩阵相乘的方式也对），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、http://poj.org/problem?id=1651

2、题目大意：

给出n个数，现在要将这些数一个一个的取出来，但是不能取出两个端点的数字，取出第i个数字（c[i]）的代价是

c[i-1]*c[i]*c[i+1]

用矩阵相乘的思想dp[i][j]表示i到j区间取出来的代价

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+c[i]*c[k]*c[j])

3、AC代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 105
#define INF 0x7ffffff
int c[N];
int dp[N][N];
int main()
{int n,tmp;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%d",&c[i]);for(int i=1;i<=n;i++)dp[i][i]=0;for(int i=2;i<=n;i++){for(int j=1;j+i<=n;j++){dp[j][j+i]=INF;for(int k=j;k<i+j;k++){dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i]+c[j]*c[k]*c[j+i]);}}}printf("%d\n",dp[1][n]);}return 0;
}
/*
5
10 1 50 20 5
*/

 

这篇关于poj 1651 Multiplication Puzzle（区间DP，直接用矩阵相乘的方式也对）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---