BZOJ1084 [SCOI2005]最大子矩阵

2015.01.20 09:52 Tue| 3 visits oi_2015| 2015_刷题日常| Text

Solution

多么可爱的题啊!! >o<

由于 $m \ge 2$,于是分类讨论乱搞出解。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 105
#define K 11

int n, m, k, s[N][3];

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()
{
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      s[i][j] = s[i-1][j] + read();
  if (m == 1)
  {
    static int f[N][K];
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j) {
        f[i][j] = f[i-1][j];
        for (int p = 0; p < i; ++p)
          f[i][j] = max(f[i][j], f[p][j-1] + s[i][1] - s[p][1]);
      }
    cout << f[n][k] << endl;
  }
  else
  {
    static int f[N][N][K];
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        for (int p = 1; p <= k; ++p) {
          f[i][j][p] = max(f[i-1][j][p], f[i][j-1][p]);
          for (int q = 0; q < i; ++q)
            f[i][j][p] = max(f[i][j][p], f[q][j][p-1] + s[i][1] - s[q][1]);
          for (int q = 0; q < j; ++q)
            f[i][j][p] = max(f[i][j][p], f[i][q][p-1] + s[j][2] - s[q][2]);
          if (i == j)
            for (int q = 0; q < min(i, j); ++q)
              f[i][j][p] = max(f[i][j][p],
                  f[q][q][p-1] + s[i][1] - s[q][1] + s[j][2] - s[q][2]);
        }
    cout << f[n][n][k] << endl;
  }
}