Comment

Huhu_Miao: 2025-05-08 10:05:35

/**
 *    author:  Huhu_Miao
 *    created: 2025.5.8 10:05:18 (UTC+8)
**/

#include<iostream>
#include<utility>

using pii = std::pair<int,int>;

#define row first;
#define col second;

constexpr int N = 501;

struct node{
	int cost;
	pii mat_size;
};

node dp[N][N];
pii mat[N];

void solve(){
	int n ;
	std::cin >> n;
	for(int i = 1; i <= n ; i++){
		auto & [r , c] = mat[i];
		std::cin >> r >> c;
	}

	for(int i = 1 ; i <= n ; i++){
		dp[i][i].cost = 0;
		dp[i][i].mat_size = mat[i];
	}

	for(int len = 2 ; len <= n ; len++){
		for(int lo = 1 ; lo <= n - len + 1 ; lo++){
			int hi = lo + len - 1;	//[lo ,hi]
			int min = 1e9;
			pii size;
			//[lo , pivot - 1] * [pivot , hi]
			for(int pivot = lo + 1; pivot <= hi ; pivot++){
				int r = dp[lo][pivot-1].mat_size.row;
				int s = dp[lo][pivot-1].mat_size.col;
				int t = dp[pivot][hi].mat_size.col;
				int cost = dp[lo][pivot - 1].cost + dp[pivot][hi].cost + r*s*t;
				if(cost < min){
					min = cost;
					size = {r , t};
				}
			}
			dp[lo][hi].cost = min;
			dp[lo][hi].mat_size = size;
		}
	}

	std::cout << dp[1][n].cost << '\n';
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

cleardream: 2025-05-08 10:02:19

C++, C, java, python就硬试，总会有AC的（赞.jpg）

cleardream: 2025-05-08 09:57:01

OK了孩子们，现在python也RE了（我没意见.jpg）

kkkztx: 2024-10-27 10:55:13

我笑了，是不是只要是python，就算代码对也是runtime error

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; 
}