洛谷P2331 [SCOI2005]最大子矩阵题解

题目链接：P2331 [SCOI2005]最大子矩阵

题意：

这里有一个 \(n\times m\) 的矩阵，请你选出其中 \(d\) 个子矩阵，使得这个 \(d\) 个子矩阵分值之和最大。注意：选出的 \(d\) 个子矩阵不能相互重叠。

输入格式：

第一行为 \(n,m,d~(1\le n\le 100,~1\le m\le 2,~1\le d\le 10)\) ，接下来 \(n\) 行描述矩阵每行中的每个元素的分值（每个元素的分值的绝对值不超过 \(32767\) ）。

输出格式：

只有一行为 \(d\) 个子矩阵分值之和最大为多少。

注意到 \(m\) 最多只有 \(2\) ，因此分别讨论

下文中用 \(a\uparrow b+c\) 表示 \(a\leftarrow \max\{a,b+c\}\)。

当 \(m=1\) 时，

题目转化为限制个数不超过 \(d\) 个的最大子段和

设 \(g_{i,j}\) 表示只考虑前 \(i\) 个数分了 \(j\) 个矩形（子段）的最大价值，则 \[ g_{i,j} = \max\left\{g_{k,j-1} + S_i-S_{k-1},~g_{i-1,j}\right\} \] 其中 \(S_i\) 为前缀和，即 \(S_i = \sum_{j=1}^{i}a_j\)

这个还是比较简单的，时间复杂度 \(O(n^2k)\)

当 \(m=2\) 时，

设 \(f_{i,j,k}\) 表示考虑第一列前 \(i\) 个数，第二列前 \(j\) 个数，花费 \(k\) 的矩形的答案。

记 \(S_{i,j}\) 表示第 \(j~(j=1,2)\) 列的前缀和，即 \(S_{i,j} = \sum_{k=1}^{i}a_{k,j}\) 。

考虑转移

啥也不干 \[ f_{i,j,k} \uparrow \max\{f_{i-1,j,k},f_{i,j-1,k}\} \]
仅选取第一列的某段区间 \[ f_{i,j,k} \uparrow \max_{1 \le l < i} \left\{f_{l,j,k-1} + S_{i,1} - S_{l-1,1}\right\} \]
仅选取第二列的某段区间 \[ f_{i,j,k} \uparrow \max_{1 \le l < j} \left\{f_{i,l,k-1} + S_{j,2} - S_{l-1,2}\right\} \]
特别地，当 \(i=j\) 时，可以选一段大矩形 \[ f_{i,j,k} \uparrow \max_{1 \le l < i}\{f_{l,l,k-1}+S_{i,1}+S_{i,2}-S_{l-1,1}-S_{l-1,2}\} \]

时间复杂度 \(O(n^3k)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(115))
#define M ((int)(15))

int n,m,d,s1[N],s2[N],f[N][N][M],g[N][M];
void up(int &x,int y) { x < y ? x = y : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> d;
    if(m == 1)
    {
        for(int i=1,x; i<=n; i++) cin >> x, s1[i] = s1[i-1] + x;
        for(int k=1; k<=d; k++)
            for(int i=1; i<=n; i++)
            {
                g[i][k] = g[i-1][k];
                for(int j=0; j<i; j++) up(g[i][k], g[j][k-1] + s1[i] - s1[j]);
            }
        cout << g[n][d] << '\n';
    }else
    {
        for(int i=1,x,y; i<=n; i++)
            cin >> x >> y, s1[i] = s1[i-1] + x, s2[i] = s2[i-1] + y;
        for(int k=1; k<=d; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                {
                    up(f[i][j][k]=f[i-1][j][k], f[i][j-1][k]);
                    for(int l=0; l<i; l++) up(f[i][j][k], f[l][j][k-1] + s1[i] - s1[l]);
                    for(int l=0; l<j; l++) up(f[i][j][k], f[i][l][k-1] + s2[j] - s2[l]);
                    if(i == j) for(int l=0; l<i; l++) up(f[i][j][k], f[l][l][k-1] + s1[i] - s1[l] + s2[j] - s2[l]);
                }
        cout << f[n][n][d] << '\n';
    }
    return 0;
}