题解 | 矩阵取数-NOIP2007提高组复赛

算法知识点: 区间DP，高精度

复杂度：

解题思路：

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

状态计算：将 所表示的所有取法分成两类：

• 先取左端点。这一类的最大分值是 ，其中 是第 个数的值。
• 先取右端点。这一类的最大分值是 ，其中 是第 个数的值。

则 就是这两类的较大值。

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;
}