nyoj 536 开心的mdd(最优矩阵链乘)dp

不念不忘少年蓝@ 2024-02-17 19:32 21阅读 0赞

### 开心的mdd ###

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

himdd有一天闲着无聊，随手拿了一本书，随手翻到一页，上面描述了一个神奇的问题，貌似是一个和矩阵有关的东西。

给出三个矩阵和其行列A1（10\*100），A2（100\*5），A3（5\*50）。现在himdd要算出计算矩阵所要的乘法次数，他发现不同的计算次序，所要的乘法次数也不一样，

如：

(A1\*A2)\*A3 : 10\*100\*5+5\*10\*50=7500;

A1\*(A2\*A3) : 5\*100\*50+10\*100\*50 =75000;

他想知道计算矩阵所要的最少乘法次数是多少，很快一个解法就诞生了，有点小happy~~现在他想问问你是否也能找出一个解法呢？

注意：矩阵不可改变顺序。

输入

有多组测试数据（<=100)，每组表述如下：  
第一行，有一个整数n矩阵的个数（1<=n<=100)  
接下来有n行  
第i行有两整数，r,c表示第i个矩阵的行列;(1<=r,c<=100)

输出

输出计算矩阵所要的最少乘法次数。

样例输入

3
    10 100
    100 5
    5 50

样例输出

7500

分析：本题类型是最优矩阵链乘问题，状态方程dp(i,j)=min(dp(i,k)+dp(k+1,j)+r\[i\]\*c\[k\]\*c\[j\]);其中（0<k<n-1）；记忆化搜索

AC代码;

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 2147483647
    const int maxn=100+10;
    int r[maxn],c[maxn];
    int d[maxn][maxn];
    int n;
    int dp(int i,int j){
    	int& ans=d[i][j];
    	if(ans>0)return ans;
    	if(i>=j)return 0;
    	if(j==i+1)return r[i]*c[i]*c[j];
    	ans=INF;
    	for(int k=i;k<j;k++)
    	ans=min(ans,dp(i,k)+dp(k+1,j)+r[i]*c[k]*c[j]);
    	return ans; 
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		for(int i=0;i<n;i++)
    		 scanf("%d%d",&r[i],&c[i]);
    		
    	 memset(d,0,sizeof(d));
    	 
    	 int ans=INF;
    	 for(int k=0;k<n;k++){
    	 	ans=min(ans,dp(0,k)+dp(k+1,n-1)+r[0]*c[k]*c[n-1]);
    	 }
    	 printf("%d\n",ans);
    	}
    	return 0;
    }

递推求解：

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 2147483647
    const int maxn=100+10;
    int r[maxn],c[maxn];
    int dp[maxn][maxn];
    int n;
    
    int main(){
    	while(scanf("%d",&n)==1){
    		for(int i=1;i<=n;i++)
    		 {
    		 scanf("%d%d",&r[i],&c[i]);
    		 dp[i][i]=0;
    		}
    	 
    	for(int len=2;len<=n;len++)   //长度 
    	 for(int i=1;i<=n-len+1;i++){ //起点 
    	 	int j=i+len-1;   //终点 
    	 	dp[i][j]=INF;
    	  for(int k=i;k<=j;k++)
    	 	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j]);
    	}
    	
    		 printf("%d\n",dp[1][n]);
      }
    	return 0;
    }