Comment

vegness: 2026-04-29 11:05:43

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static ll dp[505][505]; 
static ll r[505], c[505];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M;
    cin >> M;

    while (M--)
    {
        int N;
        cin >> N;

        for (int i = 0; i < N; i++)
            cin >> r[i] >> c[i];

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                dp[i][j] = (i == j ? 0 : LLONG_MAX);
            }
        }

        for (int len = 1; len < N; len++)
        {
            for (int i = 0; i + len < N; i++)
            {
                int j = i + len;

                for (int k = i; k < j; k++)
                {
                    if (dp[i][k] == LLONG_MAX || dp[k + 1][j] == LLONG_MAX)
                        continue;

                    ll cost = dp[i][k] + dp[k + 1][j]
                            + 1LL * r[i] * c[k] * c[j];

                    if (cost < dp[i][j])
                        dp[i][j] = cost;
                }
            }
        }

        cout << dp[0][N - 1] << '\n';
    }

    return 0;
}

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