1. 题目

传送门= ̄ω ̄=

2. 题解

MMP

巨大坑点!——

空矩阵也是子矩阵!

也就是说题目可以转换成——

选择至多 k 个子矩阵互不重叠使得所选部分权值之和最大。

正文

貌似还有一些什么 $O(n^2k)$啊之类的题解

好像甚至还有 $O(n^4)$的算法?

不清楚

我用的是记忆化搜索,代码冗长,但是复杂度是 $O(nk)$的

复杂度还是很优秀的吧 QvQ

对于 m=1

首先规定 $a$表示原矩阵,$a[i,j]$表示矩阵第 $i$行第 $j$列的数字($i$从 $1$开始,$j$从 $0$开始)。

设 $f[i,j,k]$表示当前 Dp 到第 $i$行且第 $i$行的决策为 $k$且已经建立了 $j$个子矩阵。

$k=0$或 $1$,其中 $0$表示不选择第 $i$行的那个数字,$1$表示选择。

$j$只是新建了多少个子矩阵,其中可能有未完成的矩阵(还要往里面添加数字),也有可能有已经完成的矩阵。

现在我们需要分类讨论:

(1) 当前为第 $i$行,且选择这一行

这种情况下,如果不选择下一行,那么 $f[i,j,1]=f[i+1,j,0]+a[i,0]$

如果选择下一行,那我们有两种决策:一是把下一行合并到第 $i$行的矩阵里来,二是把下一行作为一个新的矩阵的开头。

那么 $f[i,j,1]=max(f[i+1,j,1],f[i+1,j+1,1])+a[i,0]$

综上:$f[i,j,1]=max(f[i+1,j,0],f[i+1,j,1],f[i+1,j+1,1])+a[i,0]$

(2) 当前为第 $i$行,且不选择这一行

这种情况下,如果不选择下一行,那么 $f[i,j,0]=f[i+1,j,0]$

如果选择下一行,因为必须新建一个矩阵,所以 $f[i,j,0]=f[i+1,j+1,1]$

综上:$f[i,j,0]=max(f[i+1,j,0],f[i+1,j+1,1])$

这样我们就得到了 $m=1$时的递推式

对于 m=2

我们可以仿照 $m=1$的时候的做法

对于状态的设定依然是(不用仔细看了和 $m=1$的是一样的我复制过来的 QvQ):

设 $f[i,j,k]$表示当前 Dp 到第 $i$行且第 $i$行的决策为 $k$且已经建立了 $j$个子矩阵。

(注意这下面不一样了=。=)

对于 $k$,我们这样设定:

$k$の取值 所代表意义
0 这一行两个数字都不选
1 选择这一行左边的不选择右边的
2 选择这一行右边的不选择左边的
3 选择这一行的两个数字且合并到一个矩阵内
4 选择这一行的两个数字且分开作为两个矩阵看待

接着,我们依然需要分类讨论。

(1) $k=0$,这一行两个数字都不选

此时下一行的决策有如下几种情况:

  • 不选择下一行,$f[i,j,0]=f[i+1,j,0]$
  • 选择下一行的左边不选择右边:$f[i,j,0]=f[i+1,j+1,1]$
  • 选择下一行的右边不选择左边:$f[i,j,0]=f[i+1,j+1,2]$
  • 选择下一行的两个并放到一个矩形内:$f[i,j,0]=f[i+1,j+1,3]$
  • 选择下一行的两个并不放到一个矩形内:$f[i,j,0]=f[i+1,j+2,4]$

取 $max$即可

(2) $k=1$,选择这一行左边的不选择右边的

此时下一行的决策有如下几种情况:

  • 不选择下一行,$f[i,j,1]=f[i+1,j,0]+a[i,0]$
  • 选择下一行的左边不选择右边:$f[i,j,1]=max(f[i+1,j,1],f[i+1,j+1,1])+a[i,0]$(因为可以将下一行合并到当前行作为一个矩阵也可以新建矩阵)
  • 选择下一行的右边不选择左边:$f[i,j,1]=f[i+1,j+1,2]+a[i,0]$
  • 选择下一行的两个并放到一个矩形内:$f[i,j,1]=f[i+1,j+1,3]+a[i,0]$(因为此时下一行是一个完整的宽度为 2 的矩形,无法合并到当前行)
  • 选择下一行的两个并不放到一个矩形内:$f[i,j,1]=max(f[i+1,j+1,4],f[i+1,j+2,4])+a[i,0]$(因为此时下一行会出现两个小的分开的格子,可以将左边的那个合并到当前行,也可以将两个都视作新建的矩阵)

依然是取 $max$

(3) $k=2$,选择这一行右边的不选择左边的

此时下一行的决策有如下几种情况:

  • 不选择下一行,$f[i,j,2]=f[i+1,j,0]+a[i,1]$
  • 选择下一行的左边不选择右边:$f[i,j,2]=f[i+1,j+1,1]+a[i,1]$
  • 选择下一行的右边不选择左边:$f[i,j,2]=max(f[i+1,j,2],f[i+1,j+1,2])+a[i,1]$(因为可以将下一行合并到当前行作为一个矩阵也可以新建矩阵)
  • 选择下一行的两个并放到一个矩形内:$f[i,j,2]=f[i+1,j+1,3]+a[i,1]$(因为此时下一行是一个完整的宽度为 2 的矩形,无法合并到当前行)
  • 选择下一行的两个并不放到一个矩形内:$f[i,j,2]=max(f[i+1,j+1,4],f[i+1,j+2,4])+a[i,1]$(因为此时下一行会出现两个小的分开的格子,可以将右边的那个合并到当前行,也可以将两个都视作新建的矩阵)

还是取 $max$

(4) $k=3$,选择这一行的两个数字且合并到一个矩阵内

  • 不选择下一行,$f[i,j,3]=f[i+1,j,0]+a[i,0]+a[i,1]$
  • 选择下一行的左边不选择右边:$f[i,j,3]=f[i+1,j+1,1]+a[i,0]+a[i,1]$
  • 选择下一行的右边不选择左边:$f[i,j,3]=f[i+1,j+1,2]+a[i,0]+a[i,1]$
  • 选择下一行的两个并放到一个矩形内:$f[i,j,3]=max(f[i+1,j,3],f[i+1,j+1,3])+a[i,0]+a[i,1]$
  • 选择下一行的两个并不放到一个矩形内:$f[i,j,3]=f[i+1,j+2,4]+a[i,0]+a[i,1]$(虽然它们都选择一行的两个,但是是不能合并的!)

继续取 $max$

(4) $k=4$,选择这一行的两个数字且分开作为两个矩阵看待

  • 不选择下一行,$f[i,j,4]=f[i+1,j,0]+a[i,0]+a[i,1]$
  • 选择下一行的左边不选择右边:$f[i,j,4]=max(f[i+1,j,1],f[i+1,j+1,1])+a[i,0]+a[i,1]$
  • 选择下一行的右边不选择左边:$f[i,j,4]=max(f[i+1,j,2],f[i+1,j+1,2])+a[i,0]+a[i,1]$
  • 选择下一行的两个并放到一个矩形内:$f[i,j,4]=f[i+1,j+1,3]+a[i,0]+a[i,1]$
  • 选择下一行的两个并不放到一个矩形内:$f[i,j,4]=max(f[i+1,j,4],f[i+1,j+1,4],f[i+1,j+2,4])+a[i,0]+a[i,1]$(可以选择合并两个矩形、合并其中一个或者一个都不合并)

QvQ 仍然取 $max$

经过艰苦卓绝的分类讨论,我们得到了 $m=2$时的递推式

很显然,复杂度是 $O(nk)$的!

至此,我们就可以写出这题的代码啦!

代码:

#include <bits/stdc++.h>

#define NS (105)
#define KS (15)
#define INF (10000000)
#define MEM (-2122219135)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, k, arr[NS][2], f[NS][KS][5];

int Dp1(int a, int s, int c)
{
    if (s > k) return -INF;
    if (a > n) return 0;
    int& F = f[a][s][c];
    if (F != MEM) return F;
    if (c == 1)
    {
        F = max(Dp1(a + 1, s, 1), Dp1(a + 1, s + 1, 1));
        F = max(F, Dp1(a + 1, s, 0)) + arr[a][0];
        return F;
    }
        F = max(Dp1(a + 1, s + 1, 1), Dp1(a + 1, s, 0));
        return F;
}

int Dp2(int a, int s, int c)
{
    if (s > k) return -INF;
    if (a > n) return 0;
    int& F = f[a][s][c];
    if (F != MEM) return F;
    if (c == 0)
    {
        F = max(Dp2(a + 1, s, 0), Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s + 2, 4));
        return F;
    }
    if (c == 1)
    {
        F = max(Dp2(a + 1, s, 1), Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s + 1, 4));
        F = max(F, Dp2(a + 1, s + 2, 4)) + arr[a][0];
        return F; 
    }
    if (c == 2)
    {
        F = max(Dp2(a + 1, s, 2), Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s + 1, 4));
        F = max(F, Dp2(a + 1, s + 2, 4)) + arr[a][1];
        return F; 
    }
    if (c == 3)
    {
        F = max(Dp2(a + 1, s, 3), Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 2, 4)) + arr[a][0] + arr[a][1];
        return F; 
    }
        F = max(Dp2(a + 1, s, 4), Dp2(a + 1, s + 1, 4));
        F = max(F, Dp2(a + 1, s + 2, 4));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s, 1));
        F = max(F, Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s, 2));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 1, 3)) + arr[a][0] + arr[a][1];
        return F;
}

int main (int argc, char const* argv[])
{
    IN(n), IN(m), IN(k), memset(f, -127, sizeof(f));
    for (int i = 1; i <= n; i += 1)
        for (int j = 0; j < m; j += 1)
            IN(arr[i][j]);
    if (m == 1) printf("%d\n", max(Dp1(1, 1, 1), Dp1(1, 0, 0)));
    else
    {
        int ans = max(Dp2(1, 0, 0), Dp2(1, 1, 1));
        ans = max(ans, Dp2(1, 2, 1));
        ans = max(ans, Dp2(1, 3, 1));
        ans = max(ans, Dp2(1, 4, 2));
        printf("%d\n", ans);
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

3 条评论

boshi · 2018年2月11日 1:41 下午

写的真详细,兹瓷兹瓷

    konnyakuxzy · 2018年2月11日 4:51 下午

    QvQ
    因为当时我也想了很久啊
    而且被坑了更久
    QvQ

TPLY · 2018年2月10日 2:34 下午

有好像一篇论文是讲最大子矩阵的
最大子矩阵好像是有两种特别求法
mmp 我研究了一天

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注