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