P2331 [SCOI2005]最大子矩阵

YorkWu

March 11, 2019

1177 views

No comments

1265 words

P2331 [SCOI2005]最大子矩阵

#### 题目描述

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

#### 输入输出格式

##### 输入格式：

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

##### 输出格式：

只有一行为k个子矩阵分值之和最大为多少。 [题目链接](https://www.luogu.org/problemnew/show/P2331 "题目链接")

#### 思路

*   首先，可以注意到，m只能为1或2，那不妨分情况讨论。
*   当m=1时，可以发现答案即最大连续字段和，设计状态$dp(i,j)$表示从前i个元素里选择j个矩形的最大和，因此状态转移方程： 若选，$dp(i,j)=max(dp(len,j-1)+sum\[i\]-sum\[j-1\])$ 若不选，$dp(i,j)=max(dp(i,j),dp(i-1,j))$
    
*   当m=2时，$dp(i,j,k)$表示第一列前i个元素，第二列前j个元素，一共选择k个矩阵所得的最大值，因此状态转移方程分四种情况：
    
    1.  当两列均不选时：$dp(i,j,k)=max(dp(i,j-1,k),dp(i-1,j,k))$
    2.  当只选择第一列时，$dp(i,j,k)=max(dp(len,j,k-1)+sum\_1\[i\]-sum\_1\[len-1\]),len\\in\[1,i)$
    3.  当只选择第二列时，$dp(i,j,k)=max(dp(i,len,k-1)+sum\_2\[j\]-sum\_2\[len-1\]),len\\in\[1,j)$
    4.  当$i=j$时，两列都选，$dp(i,j,k)=max(dp(len,len,k-1)+sum\_1\[i\]-sum\_1\[len-1\]+sum\_2\[j\]-sum\_2\[len-1\])$ **最后这四种情况取最大值。**

#### 代码如下：

#include<bits/stdc++.h>
    using namespace std;
    int n,m,k;
    int sum1[109],sum2[109],dp1[109][15],f[109][109][15];
    
    int main(){
        cin>>n>>m>>k;
        if(m==1){
            for(int i=1;i<=n;i++){
                int x;
                cin>>x;
                sum1[i]=sum1[i-1]+x;
            }
            for(int len=1;len<=k;len++){
                for(int i=1;i<=n;i++){
                    dp1[i][len]=dp1[i-1][len];
                    for(int j=0;j<i;j++){
                        dp1[i][len]=max(dp1[i][len],dp1[j][len-1]+sum1[i]-sum1[j]);
                    }
                }
            }
            cout<<dp1[n][k];
        }
        else{
            for(int i=1;i<=n;i++){
                cin>>sum1[i]>>sum2[i];
                sum1[i]+=sum1[i-1];
                sum2[i]+=sum2[i-1];
            }
            for(int len=1;len<=k;len++){
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        f[i][j][len]=max(f[i-1][j][len],f[i][j-1][len]);
                        for(int l=0;l<i;l++) f[i][j][len]=max(f[i][j][len],f[l][j][len-1]+sum1[i]-sum1[l]);
                        for(int l=0;l<j;l++) f[i][j][len]=max(f[i][j][len],f[i][l][len-1]+sum2[j]-sum2[l]);
                        if(i==j)  for(int l=0;l<i;l++) f[i][j][len]=max(f[i][j][len],f[l][l][len-1]+sum1[i]-sum1[l]+sum2[j]-sum2[l]);
                    }
                }
            }
            cout<<f[n][n][k];
        }
        return 0;
    }

Last modification：March 14, 2020