题解 P2331 【[SCOI2005]最大子矩阵】

天泽龟 · 2019-08-23 13:45:01 · 题解

来写一个十分详细的，且码风适宜的题解。。

其实这道题没有讲的价值，只有自己写的价值。。在众多状态的转移之间能否理清自己的思路，这很重要。

写的时候确实挺爽的，拍了五六次才把所有状态弄清楚，写拙文一篇，以此记之。

• 对于M=1

首先看题目我们注意到m<=2是个很重要的约束，我们不如将两种情况分开，先考虑m=1再将其推广到m=2。

首先可以想到用i表示到了第i行，j表示已经分了j栏，但如何考虑将j栏单独分离呢？我们可以再设一维[0/1]，表示当前行是否选择，这样f[i][j][0/1]即为此状态下的最大价值。

• 那么对于f[i][j][0]，可知前一行的状态咋样都无所谓，反正我这行又不选，于是：f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])

• 对于f[i][j][1]，我们有三种可能：上一行与下一行合并，上一行是空的且当前行重起炉灶，上一行非空的但当前行重起炉灶。

（这里涉及到一些作者写题时瞎编的术语，意思大概就是合并=和上一行状态合并成一个大矩阵，重启炉灶=重开一个矩阵，当前行是矩阵的首位，感觉这样讲方便些。。）

于是可得到方程：f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][1],f[i-1][j-1][0])

以上三项分别与上面对应，其中第二项保证当矩阵不够k个时，可以通过拆分矩阵将其凑到k个，所以空矩阵其实是不存在的。。

• 对于M=2

如果我们沿用上面的那种思想，是否也可以写出第二种情况的转移方程呢？我们可以试试在第三维上面做做文章。

第三维原来描述的是当前行的状态情况，我们不如类比的来设S\in [0,4]为当前行的五种状态，分别是：

【0->当前行为空】； 【(01)_2->选右边】；【(10)_ 2->选左边】；

【(11)_ 2->都选，作为整体】；【(11)_2^*->都选，但两边分开考虑】；

其中第五个状态最不好想，我是通过对拍拍了一个数据才想到的：

4 2 2
-5 4
3  5
5  2
8  -10

貌似就是样例的升级版，但是只有第五种状态才可以符合这种类型的转移。

那么我们对其分别分析：

1. 对于S=0,类比M=1的转移情况，可知前一行的状态咋样都无所谓，反正我这行又不选，于是： f[i][j][0]=forq~~max(f[i-1][j][q])

这里我们define forq for(int q=0;q<=4;q++)，这样看不会感到很清爽吗。（笑

2. 对于S=1,我们就要重新考虑其转移了：

• 首先如果选用合并的话，可以想到前一行S=1的状态显然可以的，而且对于前一行S=4应该也可以的，于是可以得到：

• 如果选用的是重起炉灶，那么显然和上一行状态又没啥关系了，于是可得：

3. 对于S=2,，类比S=1的情况，也可以得到两个方程：

这个是合并的情况，由于S=4的定义本身就是当前行两个全选且两行分别独立，所以不论下一行接在左还是右并不会有什么问题。

这是重起炉灶的情况。

4. 对于S=3,就有些不同之处了。

首先S=4是不能通过合并转移过来的，虽然从整体图案上看还是一个矩阵，但其实已经和你的定义矛盾了。那么对于新的方程：

但是对于重起炉灶并没有啥关系，重开一个矩阵是很暴力的手法，直接转移就完事儿了。

但是要注意，这里新增的价值都变成了g[i][1]+g[i][2]，原因就不必说了吧。

5. 对于S=4,同样有些不同。

我们先感性地考虑一下S=4可从哪些方面转移而来，显然对于S=1,S=2都是可以的，但是特别的，它们都只能和当前行的单独一列合并，所以要多增加一栏存新的，第二维要标记为[j-1]：

当然也可从自身转移，当然也就不必新开一栏，就是我之前举的那个样例：

就此S=4也没了，等等，重启炉灶咋没了呢？？

哦，因为我一开始A了但没考虑这种情况，后来想想发现这次要开两个炉子贡献不是很大，所以转移时候就没涉及到，感觉硬要写的话只能表示成这样：

至此所有状态转移就完了，其实上代码没啥意思，但出于完整性还是给大家看一下我丑陋的代码吧。。

#include <iostream>
#include <cstring>
#define forq for(int q=0;q<=4;q++)  
using namespace std;
int n,m,k,ans=-2147483647,f[200][20][5],g[200][200]; 
//类比m=1，不难得出f[i][j][S]表示到第i行，分出j栏，当前行的状态
//S=0->none;  S=1-> right;  S=2->left;  
//S=3->both as a whole;  S=4->both but individual

int main()
{
    cin>>n>>m>>k; memset(f,-0x3f,sizeof(f));
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++) cin>>g[i][j];
    for (int i=1;i<4;i++) f[0][0][i]=0;
    if (m==1)
{
    for (int i=1;i<=n;i++)
    for (int j=0;j<=k;j++) //有可能到i时候还一个都不选，从0开始 
    {
        f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
        if (j) f[i][j][1]=max(f[i-1][j][1],max(f[i-1][j-1][0],f[i-1][j-1][1]))+g[i][1];//两个状态 
    }
    cout<<max(f[n][k][0],f[n][k][1])<<endl;
}
else {
    for (int i=1;i<=n;i++)
    for (int j=0;j<=k;j++)
    {
        forq f[i][j][0]=max(f[i][j][0],f[i-1][j][q]);
        if (j){
             f[i][j][1]=max(f[i][j][1],max(f[i-1][j][1],f[i-1][j][4])+g[i][2]);  
        forq f[i][j][1]=max(f[i][j][1],f[i-1][j-1][q]+g[i][2]);
        }       
        if (j){
             f[i][j][2]=max(f[i][j][2],max(f[i-1][j][2],f[i-1][j][4])+g[i][1]);
        forq f[i][j][2]=max(f[i][j][2],f[i-1][j-1][q]+g[i][1]);

        }
        if (j){
             f[i][j][3]=max(f[i][j][3],f[i-1][j][3]+g[i][1]+g[i][2]); //合并 
        forq f[i][j][3]=max(f[i][j][3],f[i-1][j-1][q]+g[i][1]+g[i][2]); //重起炉灶 
        }   
        if (j>1){ //想想看也应该从2个栏开始转移了。。 
             f[i][j][4]=max(f[i][j][4],max(max(f[i-1][j-1][1],f[i-1][j-1][2]),f[i-1][j][4])+g[i][1]+g[i][2]);
        for(int q=0;q<=4;q++)
             f[i][j][4]=max(f[i][j][4],f[i-1][j-2][q]+g[i][1]+g[i][2]); //重起炉灶 
        } 
    }
    for (int j=0;j<=4;j++) ans=max(ans,f[n][k][j]);
    cout<<ans<<endl;
}
}

思路还是挺清晰的吧，代码也不长，看在我写了近一个小时的份上给个赞吧QAQ。