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;
}