//此题实际上是一个矩阵连乘问题
//dp[i][j]=min{dp[i][k-1]+dp[k+1][j]+arr[k]*arr[i-1]*arr[j+1] | k}
#include<iostream>
using namespace std;

const int INFINITY=200000000;

int arr[100];
int dp[100][100];
int main()
{
	//freopen("input.txt","r",stdin);
	memset(dp,0,sizeof(dp));
	int i,j,k;
	int length;
	int n;
	int Min,temp;
	cin>>n;
	for(i=0;i<n;i++) cin>>arr[i];
	for(i=1;i<n-1;i++) dp[i][i]=arr[i-1]*arr[i]*arr[i+1];
	for(length=2;length<=n-2;length++){
		for(i=1,j=i+length-1 ; j<=n-2 ; i++,j++){
			Min=INFINITY;
			for(k=i;k<=j;k++){
				temp=dp[i][k-1]+dp[k+1][j]+arr[k]*arr[i-1]*arr[j+1];
				Min=(temp<Min)?temp:Min;
			}
			dp[i][j]=Min;
		}
	}
	cout<<dp[1][n-2]<<endl;
	return 0;
}

• Re:给的数据过了，怎是wa啊 (777) Calciver 2012-03-13 19:44:08