洛谷2331 [SCOI2005]最大子矩阵

题意

在 $n(n\le 100)\times m(m\le 2)$ 的矩阵中选出 $k(k\le 10)$ 个子矩阵，使得这些子矩阵中数字和最大。子矩阵之间不能重叠。

题解

如果做过 CF1199F 就很容易做出来。

用 $f[l][r][x][y][k]$ 表示在左下角为 $(l,x)$ ，右上角为 $(r,y)$ 的区域中选 $k$ 个子矩阵的最大和。枚举横纵的中间点，以及两部分选取的子矩阵的个数进行转移。

过程中需要求出这个区域中所有数的和，我最开始看数据范围小就直接暴力累加T到了60，所以还是得用前缀和。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int inf=~0x3f3f3f3f;
int n,m,k,s[105][5],sum[105][5],f[105][105][5][5][15];

int dfs(int l,int r,int x,int y,int k)
{
    int siz=(r-l+1)*(y-x+1),cur=sum[r][y]-sum[r][x-1]-sum[l-1][y]+sum[l-1][x-1];
    if (!k) return 0;
    if (siz<k) return inf;
    if (siz==k) return cur;
    int &ans=f[l][r][x][y][k];
    if (ans!=inf) return ans;
    ans=cur;
    for (int i=0;i<=k;i++)
    {
        for (int j=l;j<r;j++) ans=max(ans,dfs(l,j,x,y,i)+dfs(j+1,r,x,y,k-i));
        for (int j=x;j<y;j++) ans=max(ans,dfs(l,r,x,j,i)+dfs(l,r,j+1,y,k-i));
    }
    return ans;
}

signed main()
{
    n=read(); m=read(); k=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) s[i][j]=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) sum[i][j]=s[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    memset(f,~0x3f,sizeof(f));
    return !printf("%d",dfs(1,n,1,m,k));
}