P1073 （C++代码）

解题思路:





注意事项:





参考代码:

啦啦啦啦，我又回来啦！！！！

#include <cstdio>
#include <cstring>

struct NODE
{
    int score;
    int rft[31];

    inline NODE()
    {
        score = 1;
        rft[0] = 0;
    }

    inline NODE (const int& score, const int& no)
    {
        this->score = score;
        rft[0] = 1;
        rft[1] = no;
    }
} f[32][32];

int n;

inline NODE merge(const NODE& left, const NODE& root, const NODE& right)
{
    NODE dst(root.score, root.rft[1]);

    dst.score += left.score*right.score;
    dst.rft[0] += left.rft[0] + right.rft[0];
    memcpy(dst.rft + 2, left.rft + 1, left.rft[0]*4);
    memcpy(dst.rft + 2 + left.rft[0], right.rft + 1, right.rft[0]*4);

    return dst;
}

inline NODE max(const NODE& a, const NODE& b)
{
    return a.score > b.score ? a : b;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1, t; i <= n; i++)
    {
        scanf("%d", &t);
        f[i][i] = NODE(t, i);
    }

    for (int l = 2; l <= n; l++)
        for (int i = 1; i <= n - l + 1; i++)
            for (int j = 0; j < l - 1; j++)
                f[i][i + l - 1] = max(f[i][i + l - 1], merge(f[i][i + j - 1], f[i + j][i + j], f[i + j + 1][i + l - 1]));

    printf("%d\n", f[1][n].score);
    for (int i = 1; i <= f[1][n].rft[0]; i++)
        printf("%d ", f[1][n].rft[i]);

    return 0;
}

点赞！！！！！