洛谷P2331 [SCOI2005]最大子矩阵

题目描述

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

输入输出格式

输入格式：

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

输出格式：

只有一行为k个子矩阵分值之和最大为多少。

输入输出样例

输入样例#1： 复制

3 2 2
1 -3
2 3
-2 3

输出样例#1： 复制

9

分析

代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=105;
int n,m,k;
int dp[mxn][mxn][12],map[mxn][3],res[mxn][3],two[mxn];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;++i) 
    for(int j=1;j<=m;++j) 
        map[i][j]=read();
    for(int i=1;i<=n;++i) 
    for(int j=1;j<=m;++j) 
        res[i][j]=res[i-1][j]+map[i][j];
    for(int i=1;i<=n;++i) 
        two[i]=two[i-1]+map[i][1]+map[i][2];
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j){
        for(int p=k;p>=1;p--){
            dp[i][j][p]=max(dp[i][j-1][p],dp[i-1][j][p]);
            for(int fi=1;fi<=i;++fi) 
                dp[i][j][p]=max(dp[i][j][p],dp[fi-1][j][p-1]+res[i][1]-res[fi-1][1]);
            for(int fi=1;fi<=j;++fi) 
                dp[i][j][p]=max(dp[i][j][p],dp[i][fi-1][p-1]+res[j][2]-res[fi-1][2]);
            for(int fi=1;fi<=min(i,j);++fi)
                dp[i][j][p]=max(dp[i][j][p],dp[fi-1][fi-1][p-1]+two[min(i,j)]-two[fi-1]);
        }
    }
    printf("%d
",dp[n][n][k]);
    return 0;
}