能量项链

VecDouble · 2022-05-10 13:49:51 · 个人记录

• Link

  • P1063 [NOIP2006 提高组] 能量项链
  • \#10148.「一本通 5.1 例 2」能量项链
• Therefore,\ see\ the\ above\ question\ for\ the\ specific\ ideas\ of\ this\ question.

The\ code:

#include <bits/stdc++.h>

using namespace std;

const int N = 205;

int f[N][N], s[N][N];
int a[N], b[N], n, ans;

inline int min(int, int);
inline int max(int, int);
inline int read(void);
inline void prep(void);
inline void dp(void);

int main(void) {
    prep();
    dp();
    printf("%d", ans);

    return 0;
}

inline int read(void) {
    int res = 0;
    char c = getchar();

    for(; !isdigit(c); c = getchar());

    for(; isdigit(c); c = getchar()) {
        res = res * 10 + c - '0';
    }

    return res;
}

inline int max(int x, int y) {
    return y & ((x - y) >> 31) | x & (~(x - y) >> 31);
}

inline int min(int x, int y) {
    return x & ((x - y) >> 31) | y & (~(x - y) >> 31);
}

inline void prep(void) {
    n = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        a[i + n] = a[i];
    }

    b[2 * n] = a[1];
    for(int i = 1; i <= 2 * n - 1; ++i) {
        b[i] = a[i + 1];
    }
}

inline void dp(void) {
    for(int L = 2; L <= n; ++L) {
        for(int i = 1; i <= 2 * n - L + 1; ++i) {
            int j = i + L - 1;

            for(int k = i; k < j; ++k) {
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + a[i] * b[k] * b[j]);
            }
        }
    }

    for(int i = 1; i <= n; ++i) {
        ans = max(ans, f[i][i + n - 1]);
    }
}