前言

__int128 yyds!!!

还有初始值不能设的过大，我本来设了 $999999999999999999999999$，结果连 __int128 都爆了，WA 了一次

时间复杂度

$O(N^3)$

空间复杂度

$O(N^2)$

c++ 代码

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline
//# define int __int128
using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

int n, a[55];

__int128 dp[55][55];

string ans;

int main () {

    old_six

    cin >> n;

    for (int i = 1; i <= n; ++ i)
        cin >> a[i];

    for (int len = 2; len < n; ++ len)
        for (int l = 1, r; (r = l + len) <= n; ++ l) {

            dp[l][r] = (__int128) (LLONG_MAX - 1) * (LLONG_MAX - 1);

            for (int k = l + 1; k < r; ++ k)
                dp[l][r] = min (dp[l][r], dp[l][k] + dp[k][r] + (__int128) a[l] * a[k] * a[r]);

        }
//  cout << dp[1][n] << '\n';
    while (dp[1][n])
        ans = (char) (dp[1][n] % 10 + '0') + ans, dp[1][n] /= 10;

    cout << ans;

    return 0;

}

前言

祝大家六一快乐！！！

时间复杂度

$O(N^3)$

空间复杂度

$O(N^2)$

代码

cpp

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

int n, a[35], dp[35][35], g[35][35];

void dfs (int l, int r) {

    if (l > r)
        return ;

    cout << g[l][r] << ' ';

    dfs (l, g[l][r] - 1);

    dfs (g[l][r] + 1, r);

    return ;

}

int main () {

    old_six

    cin >> n;

    for (reg int i = 1; i <= n; ++ i)
        cin >> a[i], dp[i][i] = a[i], g[i][i] = i;

    for (reg int len = 1; len < n; ++ len)
        for (reg int l = 1, r; (r = l + len) <= n; ++ l)
            for (reg int k = l; k <= r; ++ k) {

                reg int x = (k > l ? dp[l][k - 1] : 1) * (k < r ? dp[k + 1][r] : 1) + a[k];

                if (x > dp[l][r]) {

                    dp[l][r] = x;

                    g[l][r] = k;

                }

            }

    cout << dp[1][n] << '\n';;

    dfs (1, n);

    return 0;

}

温馨提示：

数组要开两倍！！！

时间复杂度：

$O(N^3)$

空间复杂度：

$O(N^2)$

代码：

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

int n, a[205], dp[205][205], maxx;

int main () {

    old_six

    cin >> n;

    for (reg int i = 0; i < n; ++ i)
        cin >> a[i], a[i + n] = a[i];

    for (reg int len = 2, m = n << 1; len <= n; ++ len)
        for (reg int l = 0, r; (r = l + len) < m; ++ l)
            for (reg int k = l + 1; k < r; ++ k)
                dp[l][r] = max (dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);

    for (reg int i = 0; i < n; ++ i)
        maxx = max (maxx, dp[i][i + n]);

    cout << maxx;

    return 0;

}

前言

$yxc$ 太狠了，来了一道紫题！！！

注意事项

注意空间，开数组的时候不要忘记加上 1<<！！！（不然就会像我这个蒟蒻一样 RE 了 $4$ 次之后才得到一次 AC。。。）

时&空复杂度

时间复杂度：$O(N^23^N)$具体怎么算的我不知道，请自己去 $y$ 总的题解里看！！！

空间复杂度：$2^NN$

代码

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

const int inf = 0x3f3f3f3f;

int n, m, a[15][15], dp[1 << 12][15], g[1 << 12], x, y, v, minx = inf;

int main () {

    old_six

    cin >> n >> m;

    memset (a, 0x3f, sizeof a);

    memset (dp, 0x3f, sizeof dp);

    for (reg int i = 0; i < n; ++ i)
        dp[1 << i][0] = a[i][i] = 0;

    while (m --) {

        cin >> x >> y >> v;

        -- x, -- y;

        a[x][y] = a[y][x] = min (a[x][y], v);

    }

    m = 1 << n;

    for (reg int i = 1; i < m; ++ i)
        for (reg int j = 0; j < n; ++ j)
            if (i >> j & 1)
                for (reg int k = 0; k < n; ++ k)
                    if (a[j][k] < inf)
                        g[i] |= 1 << k;

    for (reg int i = 1; i < m; ++ i)
        for (reg int j = (i - 1); j; j = (j - 1) & i)
            if ((g[j] & i) == i) {

                reg int x = i ^ j, c = 0;

                for (reg int k = 0; k < n; ++ k)
                    if (x >> k & 1) {

                        int t = inf;

                        for (reg int u = 0; u < n; ++ u)
                            if (j >> u & 1)
                                t = min (t, a[k][u]);

                        c += t;

                    }

                for (reg int k = 1; k < n; ++ k)
                    dp[i][k] = min (dp[i][k], dp[j][k - 1] + c * k);

            }

    -- m;

    for (reg int i = 0; i < n; ++ i)
        minx = min (minx, dp[m][i]);

    cout << minx;

    return 0;

}

前言

$yxc$ 太狠了，来了一道紫题！！！

注意事项

注意空间，开数组的时候不要忘记加上 1<<！！！（不然就会像我这个蒟蒻一样 RE 了 $4$ 次之后才得到一次 AC。。。）

时&空复杂度

时间复杂度：$O(N^23^N)$具体怎么算的我不知道，请自己去 $y$ 总的题解里看！！！

空间复杂度：$2^NN$

代码

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

const int inf = 0x3f3f3f3f;

int n, m, a[15][15], dp[1 << 12][15], g[1 << 12], x, y, v, minx = inf;

int main () {

    old_six

    cin >> n >> m;

    memset (a, 0x3f, sizeof a);

    memset (dp, 0x3f, sizeof dp);

    for (reg int i = 0; i < n; ++ i)
        dp[1 << i][0] = a[i][i] = 0;

    while (m --) {

        cin >> x >> y >> v;

        -- x, -- y;

        a[x][y] = a[y][x] = min (a[x][y], v);

    }

    m = 1 << n;

    for (reg int i = 1; i < m; ++ i)
        for (reg int j = 0; j < n; ++ j)
            if (i >> j & 1)
                for (reg int k = 0; k < n; ++ k)
                    if (a[j][k] < inf)
                        g[i] |= 1 << k;

    for (reg int i = 1; i < m; ++ i)
        for (reg int j = (i - 1); j; j = (j - 1) & i)
            if ((g[j] & i) == i) {

                reg int x = i ^ j, c = 0;

                for (reg int k = 0; k < n; ++ k)
                    if (x >> k & 1) {

                        int t = inf;

                        for (reg int u = 0; u < n; ++ u)
                            if (j >> u & 1)
                                t = min (t, a[k][u]);

                        c += t;

                    }

                for (reg int k = 1; k < n; ++ k)
                    dp[i][k] = min (dp[i][k], dp[j][k - 1] + c * k);

            }

    -- m;

    for (reg int i = 0; i < n; ++ i)
        minx = min (minx, dp[m][i]);

    cout << minx;

    return 0;

}

警示后人

如果你用了破环成链法，你就必须数组大小乘 $2$！！！

时间复杂度：$O(N^2)$

空间复杂度：$N^2$

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

int n, a[405], d[405][405], p[405][405], minx = 1e9, maxx;

int dfs1 (int l, int r) {

    if (d[l][r] || l == r)
        return d[l][r];

    int minx = 1e9;

    for (reg int i = l; i < r; ++ i)
        minx = min (minx, dfs1 (l, i) + dfs1 (i + 1, r) + a[r] - a[l - 1]);

    return d[l][r] = minx;

}

int dfs2 (int l, int r) {

    if (p[l][r] || l == r)
        return p[l][r];

    int maxx = 0;

    for (reg int i = l; i < r; ++ i)
        maxx = max (maxx, dfs2 (l, i) + dfs2 (i + 1, r) + a[r] - a[l - 1]);

    return p[l][r] = maxx;

}

int main () {

    old_six

    cin >> n;

    for (reg int i = 1; i <= n; ++ i)
        cin >> a[i], a[i + n] = a[i], a[i] += a[i - 1];

    for (reg int i = 1; i <= n; ++ i)
        a[i + n] += a[i + n - 1];

    dfs1 (1, n << 1), dfs2 (1, n << 1);

    for (reg int i = 1; i <= n; ++ i) {

        minx = min (minx, d[i][i + n - 1]);

        maxx = max (maxx, p[i][i + n - 1]);

    }

    cout << minx << '\n' << maxx;

    return 0;

}

y总是没讲还是我没找到视频？如果有的话哪位好心人发一下链接在评论区呗~

c++

时间复杂度：$\sum\limits_{i=1}^T2^NN^2$（是不是特别怪？）

空间复杂度：$N^2+2^N$（空间复杂度一样怪。。。）

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); i ++)

# define iter(type) \
    type :: iterator

# define reg register

# define inl inline

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

const double eps = 1e-6;

int n, m, pos[20][20], dp[1 << 18], t;

pair <double, double> a[20];

int cmp (double x, double y) {

    if (fabs (x - y) < eps)
        return 0;

    if (x < y)
        return -1;

    return 1;

}

int main () {

    old_six

    cin >> t;

    while (t --) {

        cin >> n >> m;

        for (reg int i = 0; i < n; ++ i)
            cin >> a[i].first >> a[i].second;

        memset (pos, 0, sizeof pos);

        memset (dp, 0x3f, sizeof dp);

        dp[0] = 0, m = (1 << n) - 1;

        for (reg int i = 0; i < n; ++ i) {

            pos[i][i] = 1 << i;

            reg double x1 = a[i].first, y1 = a[i].second;

            for (reg int j = 0; j < n; ++ j) {

                reg double x2 = a[j].first, y2 = a[j].second;

                if (! cmp (x1, x2))
                    continue ;

                reg double x = (y1 / x1 - y2 / x2) / (x1 - x2), y = y1 / x1 - x * x1;

                if (cmp (x, 0) >= 0)
                    continue ;

                reg int t = 0;

                for (reg int k = 0; k < n; ++ k)
                    t |= ! cmp (x * a[k].first * a[k].first + y * a[k].first, a[k].second) << k;

                pos[i][j] = t;

            }

        }

        for (reg int i = 0; i < m; ++ i) {

            reg int x = 0;

            for (reg int j = 0; j < n; ++ j)
                if (! (i >> j & 1)) {

                    x = j;

                    break ;

                }

            for (reg int j = 0; j < n; ++ j)
                dp[i | pos[x][j]] = min (dp[i | pos[x][j]], dp[i] + 1);

        }

        cout << dp[m] << '\n';

    }

    return 0;

}

AcWing【AC之星】教育优惠计划！ 我的邀请码是：JALIPS