백준 소스코드 [C++] 11049 행렬 곱셈 순서

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

백준 소스코드 [C++] 11049 행렬 곱셈 순서

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
typedef long long ll;
using namespace std;
int dim[501],ans[501][501];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) cin >> dim[i] >> dim[i + 1];

	for(int dia=1;dia<=n;dia++)
		for (int i = 1;i <= n - dia;i++) {
			int j = i + dia;
			ans[i][j] = INT_MAX;
			for (int k = i;k < j;k++)
				ans[i][j] = min(ans[i][j], ans[i][k] + ans[k + 1][j] + dim[i - 1] * dim[k] * dim[j]);
		}
	cout << ans[1][n];
	return 0;
}