超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC008D解いてみた

座標圧縮はやったことなかったので練習してみます。
まず、素直に実装するとこうなる。
詰まったところ
下のような巨大な配列を何も考えずにmemsetすると凄まじい時間がかかるので、基本的にはギリギリを攻める。

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

#define MAX_N 30

using namespace std;

typedef pair<int,int> P;

int xs[MAX_N+10];
int ys[MAX_N+10];

int dp[MAX_N+10][MAX_N+10][MAX_N+10][MAX_N+10][2000];

P ps[MAX_N+10];
int W,H,N;

int dfs(int x1, int y1, int x2, int y2,int current) {
  if(dp[x1][y1][x2][y2][current]!=-1) {
    return dp[x1][y1][x2][y2][current];
  }
  int answer=0;
  for(int i=0;i<N;++i) {
    int subAnswer=0;
    int used=(current>>i)&1;
    if (used==1) {
      continue;
    }
    int x=ps[i].first;
    int y=ps[i].second;
    if (x>x1 && x<x2 && y>y1&& y<y2) {
      subAnswer +=xs[x2]-xs[x1] + ys[y2]-ys[y1]-3;
      subAnswer +=dfs(x1,y1,x,y, current | (1<<i));
      subAnswer +=dfs(x1,y,x,y2, current | (1<<i));
      subAnswer +=dfs(x,y1,x2,y, current | (1<<i));
      subAnswer +=dfs(x,y,x2,y2, current | (1<<i));
    }
    answer = max(answer, subAnswer);
  }
  return dp[x1][y1][x2][y2][current]=answer;
}

int main() {
  scanf("%d%d%d", &W, &H, &N);
  for(int i=0;i<N;++i) {
    int _x,_y;
    scanf("%d%d", &_x, &_y);
    xs[i]=_x;
    ys[i]=_y;
    ps[i].first =_x;
    ps[i].second=_y;
  }
  for(int i=0;i<=N+1;++i) {
    for(int j=0;j<=N+1;++j) {
      for(int k=0;k<=N+1;++k) {
        for(int l=0;l<=N+1;++l) {
          for(int m=0;m<(1<<N);++m) {
            dp[i][j][k][l][m] = -1;
          }
        }
      }
    }
  }
  xs[N]=0;
  ys[N]=0;
  xs[N+1]=W+1;
  ys[N+1]=H+1;
  sort(xs, xs+N+2);
  sort(ys, ys+N+2);
  for(int i=0;i<N;++i) {
    ps[i].first=lower_bound(xs,xs+N+2,ps[i].first)-xs;
    ps[i].second=lower_bound(ys,ys+N+2,ps[i].second)-ys;
  }

  printf("%d\n", dfs(0,0,N+1,N+1,0));

  return 0;
}

でも、領域のサイズがわかれば別に機械の作動状況は保存する必要がないので下のようになる。

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

#define MAX_N 30

using namespace std;

typedef pair<int,int> P;

int xs[MAX_N+10];
int ys[MAX_N+10];

int dp[MAX_N+10][MAX_N+10][MAX_N+10][MAX_N+10];

P ps[MAX_N+10];
int W,H,N;

int dfs(int x1, int y1, int x2, int y2) {
  if(dp[x1][y1][x2][y2]!=-1) {
    return dp[x1][y1][x2][y2];
  }
  int answer=0;
  for(int i=0;i<N;++i) {
    int subAnswer=0;
    int x=ps[i].first;
    int y=ps[i].second;
    if (x>x1 && x<x2 && y>y1&& y<y2) {
      subAnswer +=xs[x2]-xs[x1] + ys[y2]-ys[y1]-3;
      subAnswer +=dfs(x1,y1,x,y);
      subAnswer +=dfs(x1,y,x,y2);
      subAnswer +=dfs(x,y1,x2,y);
      subAnswer +=dfs(x,y,x2,y2);
    }
    answer = max(answer, subAnswer);
  }
  return dp[x1][y1][x2][y2]=answer;
}

int main() {
  scanf("%d%d%d", &W, &H, &N);
  for(int i=0;i<N;++i) {
    int _x,_y;
    scanf("%d%d", &_x, &_y);
    xs[i]=_x;
    ys[i]=_y;
    ps[i].first =_x;
    ps[i].second=_y;
  }
  for(int i=0;i<=N+1;++i) {
    for(int j=0;j<=N+1;++j) {
      for(int k=0;k<=N+1;++k) {
        for(int l=0;l<=N+1;++l) {
          dp[i][j][k][l] = -1;
        }
      }
    }
  }
  xs[N]=0;
  ys[N]=0;
  xs[N+1]=W+1;
  ys[N+1]=H+1;
  sort(xs, xs+N+2);
  sort(ys, ys+N+2);
  for(int i=0;i<N;++i) {
    ps[i].first=lower_bound(xs,xs+N+2,ps[i].first)-xs;
    ps[i].second=lower_bound(ys,ys+N+2,ps[i].second)-ys;
  }

  printf("%d\n", dfs(0,0,N+1,N+1));

  return 0;
}

メモ化再帰直感的でいいですね!