矩阵链乘
#include <iostream>
#include<bits/stdc++.h>
#include <algorithm>
#include <chrono>
using namespace std;
ofstream file_out, time_out;
const int maxn = 100 + 50;
double time_list[5];
void print(int s[][150], int i, int j){
if(i == j)
file_out << "A" << i;
else{
file_out << "(";
print(s, i, s[i][j]);
print(s, s[i][j] + 1, j);
file_out << ")";
}
}
int main(){
string from = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\input\\1_1_input.txt";
string dest = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\output\\result.txt";
string time = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\output\\time.txt";
ifstream file_in;
file_in.open(from);
file_out.open(dest);
time_out.open(time);
for(int i = 0; i < 5; i++){
long long nums[maxn];
long long dp[maxn][maxn];
int s[maxn][maxn];
int N;
file_in >> N;
for (int i = 0; i <= N; i++)
file_in >> nums[i];
chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
for(int i = 1; i<= N; 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] = 9223372036854775807;
for (int k = i; k < j; k++) {
long long tmp = dp[i][k] + dp[k + 1][j] + nums[i-1] * nums[k] * nums[j];
if(tmp < dp[i][j]){
dp[i][j] = tmp;
s[i][j] = k;
}
}
}
}
chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
file_out << dp[1][N] << endl;
print(s, 1, N);
file_out << endl;
chrono::duration<double> time_span = chrono::duration_cast<chrono::duration<double>>(t2 - t1);
time_list[i] = time_span.count();
if(i == 0){
for(int j = 1; j<= N; j++){
for(int l = j; l <= N; l++)
cout << "m[" << j << "][" << l << "]=" << dp[j][l] << " ";
cout << endl;
}
for(int j = 1; j<= N-1; j++){
for(int l = j+1; l <= N; l++)
cout << "s[" << j << "][" << l << "]=" << s[j][l] << " ";
cout << endl;
}
}
}
for(int i = 0; i < 5; i++){
time_out << time_list[i] << "s" << endl;
}
return 0;
}