poj-1681【矩阵连乘】

题意是：给你一序列数，每次抽出一个数字（两端除外），抽取的数乘以旁边两个数作为此次操作的积分，抽到只剩两个数为止。求总积分最小。

题目给的数据：10 1 50 50 20 5

可以看成给了 10*1 1*50 50*50 50*20 20*5这些个矩阵求矩阵连乘最少乘数

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_N 110
#define INF 0x3f3f3f3fd
int dp[MAX_N][MAX_N];
int l[MAX_N];
int r[MAX_N];
int find_min(int x,int y)
{
	return x>y?y:x;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int val;
		int i,j,k;
		for(i=0;i<n;i++)
		{
			scanf("%d",&val);
			if(i<n-1)
				l[i]=val;
			if(i>0)
				r[i-1]=val;
		}
		n-=2;
		// for(int j=0;j<n-1;j++)
		// 	printf("%d %dn",l[j],r[j]);
		memset(dp,0x3f,sizeof(dp));
		for(i=0;i<=n;i++)
			dp[i][i]=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=n-i;j++)
			{
				for(k=j;k<=j+i-1;k++)
				{
					dp[j][j+i]=find_min(dp[j][j+i],dp[j][k]+dp[k+1][j+i]+l[j]*r[k]*r[j+i]);
				}
			}
		}
		printf("%dn",dp[0][n]);
	}
	return 0;
}

最后

以上就是内向自行车为你收集整理的poj-1681【矩阵连乘】的全部内容，希望文章能够帮你解决poj-1681【矩阵连乘】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。