【題解】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;
}
分享本文 Share with friends