BZOJ 1084([SCOI2005]最大子矩阵-长矩阵Dp)

1084: [SCOI2005]最大子矩阵

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 586  Solved: 275
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

3 2 2

1 -3

2 3

-2 3

Sample Output

9

由于m不超过2
可以暴力Dp
分为m=1和m=2种情况
m=1就不用说了,
F[i][j][k]表示第1行到i第二行到j所能取到的最小值

#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN (100+10)
#define MAXM (2+1)
#define MAXK (10+1)
int f[MAXN][MAXK],F[MAXN][MAXN][MAXK],n,m,k;
int a[MAXN][MAXN],sum[MAXN][MAXN];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    sum[0][1]=sum[0][2]=0;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]),sum[i][j]=sum[i-1][j]+a[i][j];
    if (m==1)
    {
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;i++) 
        {
            f[i][0]=0;
            for (int l=1;l<=k;l++)
            {
                f[i][l]=f[i-1][l];
                for (int j=0;j<i;j++)
                {
                    f[i][l]=max(f[i][l],f[j][l-1]+sum[i][1]-sum[j][1]);
                }
            }       
        }
        cout<<f[n][k]<<endl;
    }
    else
    {
        memset(F,0,sizeof(F));
        for (int i=1;i<=n;i++) 
        {
            for (int j=1;j<=n;j++)
            {
                F[i][j][0]=0;
                for (int l=1;l<=k;l++)
                {
                    F[i][j][l]=max(F[i-1][j][l],F[i][j-1][l]);
                    for (int i2=0;i2<i;i2++) F[i][j][l]=max(F[i][j][l],F[i2][j][l-1]+sum[i][1]-sum[i2][1]);
                    for (int j2=0;j2<j;j2++) F[i][j][l]=max(F[i][j][l],F[i][j2][l-1]+sum[j][2]-sum[j2][2]);
                    if (i==j)
                        for (int j2=0;j2<i;j2++)
                        {
                            F[i][i][l]=max(F[i][i][l],F[j2][j2][l-1]+sum[i][1]-sum[j2][1]+sum[j][2]-sum[j2][2]);
                        }
                }
            }       
        }

        cout<<F[n][n][k]<<endl;

    }

    return 0;
}