算法

(区间DP,高精度) $O(nm^2)$

每一行都是独立的，因此每行可以分别算最大值。

在每一行内：

状态表示：$f[i, j]$ 表示将 [i, j] 这段数取完的所有取法的最大分值。

状态计算：将 $f[i, j]$ 所表示的所有取法分成两类：

• 先取左端点。这一类的最大分值是 $f[i + 1, j] + g[i] \times 2^{m - j + i}$，其中 $g[i]$ 是第 $i$ 个数的值。
• 先取右端点。这一类的最大分值是 $f[i, j - 1] + g[j] \times 2^{m - j + i}$，其中 $g[j]$ 是第 $j$ 个数的值。

则 $f[i, j]$ 就是这两类的较大值。

注意这道题目的高精度对效率要求较高，最好圧位计算。

时间复杂度

一共有 $m^2$ 个状态，每个状态需要 $O(1)$ 的计算量，因此每一行需要 $O(m^2)$ 的计算量，一共要计算 $n$ 行，因此总时间复杂度是 $O(nm^2)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

const int N = 90;

int n, m;
int g[N];
VI f[N][N];
VI power2[N];

VI add(VI a, VI b)
{
    static VI c;
    c.clear();
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++ )
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 100000000);
        t /= 100000000;
    }
    return c;
}

VI mul(VI A, int b)
{
    static VI C;
    C.clear();
    LL t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += (LL)A[i] * b;
        C.push_back(t % 100000000);
        t /= 100000000;
    }
    return C;
}

VI maxV(VI A, VI B)
{
    if (A.size() != B.size())
    {
        if (A.size() > B.size()) return A;
        return B;
    }
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        if (A[i] > B[i]) return A;
        if (A[i] < B[i]) return B;
    }
    return A;
}

void print(VI A)
{
    printf("%d", A.back());
    for (int i = A.size() - 2; i >= 0; i -- ) printf("%08d", A[i]);
    puts("");
}

VI work()
{
    for (int len = 1; len <= m; len ++ )
        for (int l = 1; l + len - 1 <= m; l ++ )
        {
            int r = l + len - 1;
            if (l == r) f[l][r] = mul(power2[m - len + 1], g[r]);
            else
            {
                auto left = add(mul(power2[m - len + 1], g[l]), f[l + 1][r]);
                auto right = add(mul(power2[m - len + 1], g[r]), f[l][r - 1]);
                f[l][r] = maxV(left, right);
            }
        }

    return f[1][m];
}

int main()
{
    scanf("%d%d", &n, &m);


    power2[0] = {1};
    for (int i = 1; i <= m; i ++ ) power2[i] = mul(power2[i - 1], 2);

    VI res(1, 0);
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) scanf("%d", &g[j]);
        res = add(res, work());
    }

    print(res);

    return 0;
}