Comment

2022Alia: 2022-10-16 14:32:35
//1020矩阵连乘的最小算法代价,按照样例输入计算输出结果正确，请问哪里出了问题？谢谢

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;

const int size=500;
int p[size];
int m[size][size],s[size][size];
int n;

void matrixchain(){
	int i,r,j,k;
	memset(m,0,sizeof(m));
	memset(s,0,sizeof(s));
	for(r=2;r<=n;r++){
		for(i=1;i<=n-r+1;i++){
			j=i+r-1;
			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
			s[i][j]=i; //存储决策点 
			for(k=i+1;k<j;k++){
				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; //寻找最优值 
				if(t<m[i][j]){
					m[i][j]=t;
					s[i][j]=k; //更新分割界限 
				}	 
			}
		}
	}
}


int main(){
	int M;
	cin >> M;  //共输入M组数据
	for(int i=0;i<M;i++){
		cin >> n;  //矩阵个数 
		for(int i=0;i<2*n;i++)
		cin >> p[i];
		
		int q=unique(p,p+2*n)-p;  // 去重，计算实际元素数 
		//for(int j=0;j<q;j++)
		//cout << p[j]<<" ";  //测试是否去重成功 
		matrixchain();
		cout<< m[1][n]<<endl;	
	}
	 return 0; 
}