LibreOJ 10148 能量项链

题目链接:LibreOJ 10148 能量项链

题目大意:
LibreOJ 10148 能量项链

题解:
一道典型的区间\(dp\)题。
状态转移方程:

\[dp[i][j] = max\{dp[i][j], dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]\},i\leq k < j \]

#include <iostream>
using namespace std;
#define ll long long
#define N 1010

int a[N], n;
ll dp[N][N], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[n + i] = a[i];
    }
    for (int len = 1; len < n; ++len) {
        for (int i = 1; i + len < 2 * n; ++i) {
            int j = i + len;
            dp[i][j] = 0;
            for (int k = i; k < j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dp[i][i + n - 1]);
    }
    cout << ans;
    return 0;
}
上一篇:67.校园二手交易管理系统


下一篇:图论专题100题之:「LibreOJ β Round #4」子集(二分图+基础数论)