【題解】TIOJ 1488 . D.正直DE

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1488
【解題想法】區間DP，枚舉

//
//  main.cpp
//  TIOJ 1488 1488 . D.正直DE
//  https://tioj.ck.tp.edu.tw/problems/1488
//  Created by Hsiu-Fen Chou on 2021/6/20.
//  區間DP

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1005;
long long dp[maxn][maxn];
pair <int, int> M[maxn]; //每個matrix的列數及行數
int T, N;
long long total;

long long solve(int l, int r) {
if (dp[l][r] != -1) return dp[l][r];
if (l == r) return dp[l][r] = 0;
// M[l] * M[l+1] * ... * M[r]
// 枚舉切點 i，分成左右兩半，各自進行矩陣連乘
dp[l][r] = 2e18;
for (int i = l; i < r; i++) {
dp[l][r] = min(dp[l][r], solve(l, i) + solve(i+1, r) + M[l].first * M[i].second * M[r].second);
}
return dp[l][r];
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
for (int t = 0; t < T; t++) {
cin >> N;
memset(M, 0, sizeof(M));
for (int i = 0; i < N; i++) {
cin >> M[i].first >> M[i].second;
}
memset(dp, -1, sizeof(dp));
for (int i = 0; i < N; i++) {
dp[i][i] = 0;
}
cout << (long long)ceil((double)solve(0, N-1) / 1000) << "\n";
total += dp[0][N-1];
}
cout << (long long)ceil((double)total / 1000) << "\n";
return 0;
}