IOI 2009 Bulgaria過去問 Raisins

Algorithm IOI

解法

dp[r1][c1][r2][c2] := 左上(r1, c1)、右下(r2, c2)の長方形部分をカットするときの最小コスト

としてDPすればよい。実装はメモ化再帰の方が楽だし部分問題全部解くから時間的にも問題はない。

実行時間は O(N2M2(N+M)) と大きめだが N, M <= 50 で時間制限が5秒あるので大丈夫。

ソース

/*
  TASK: Raisins (IOI 2009 Bulgaria)
  LANG: C++
  NAME: JAPLJ

  Problem URL: http://www.ioi-jp.org/ioi/2009/problems/day1/Raisins_jp.pdf
 */

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int raisinCount[64][64];
int raisinSum[64][64];
int memo[64][64][64][64];

int calcMinimum(int r1, int c1, int r2, int c2)
{
  if(memo[r1][c1][r2][c2] >= 0)
    return memo[r1][c1][r2][c2];
  if(r1 == r2 && c1 == c2) return 0;
  int& ret = memo[r1][c1][r2][c2];
  int sum = raisinSum[r2][c2] - raisinSum[r1-1][c2] - raisinSum[r2][c1-1] + raisinSum[r1-1][c1-1];
  ret = 1000000000;
  for(int y=r1; y<r2; ++y)
    ret = min(ret, calcMinimum(r1, c1, y, c2) + calcMinimum(y+1, c1, r2, c2) + sum);
  for(int x=c1; x<c2; ++x)
    ret = min(ret, calcMinimum(r1, c1, r2, x) + calcMinimum(r1, x+1, r2, c2) + sum);
  return ret;
}

int main()
{
  int N, M;
  scanf("%d%d", &N, &M);
  for(int i=1; i<=N; ++i)
    for(int j=1; j<=M; ++j)
      scanf("%d", &raisinCount[i][j]);
  for(int i=1; i<=N; ++i)
    for(int j=1; j<=M; ++j)
      raisinSum[i][j] = raisinSum[i-1][j] + raisinSum[i][j-1] - raisinSum[i-1][j-1] + raisinCount[i][j];
  memset(memo, -1, sizeof(memo));
  printf("%d\n", calcMinimum(1, 1, N, M));
  return 0;
}