AtCoder Beginner Contest #008 D問題 - 金塊ゲーム

Source

AtCoder Beginner Contest #008
問題文

問題概要

無限に広い $2$ 次元の盤面を考える.
盤面のうち $(x,y), \;\; 1 \leq x \leq W,\ 1 \leq y \leq H$ の各セルには金塊が置いてある.
また,金塊のあるマスのうち $N$ マスに金塊回収装置が置いてあり,金塊回収装置 $k$ の置いてあるマスは $(X_k, Y_k)$ である.
ここで,同じ $x$ 座標には $2$ つ以上の金塊回収装置が置いてあることはなく,同じ $y$ 座標にも $2$ つ以上の金塊回収装置が置いてあることはない.
金塊回収装置は,$1$ 度起動させると,装置のあるマスと,その上下左右それぞれに金塊があるマスが続く限り回収する.(金塊がないマスが $1$ つでもあればその方向の回収は終わる)
金塊回収装置の起動する順番を自由に選んで良いので,最大でいくつ金塊を回収できるかを求める問題.

解法

$1$ 個金塊回収装置を起動させると,領域が左上,左下,右上,右下の $4$ つに分割される.
そこで,今考えている領域の左端,右端,上端,下端を状態にしてDPすれば良い.
端は金塊回収装置の置いてあるマスの $x$ 座標,$y$ 座標のみを考えれば良いので,それぞれ $N$ 通り(最初の端も考えると $+2$ 通り)しか無い.
よって状態数は $O(N^4)$ になる.
それぞれの状態で,どの金塊回収装置を起動させるかを全部試すので,時間計算量は $O(N^5)$ 程度.

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int X, Y, N;
int x[33], y[33];
int dp[33][33][33][33];

int solve(int x1, int x2, int y1, int y2){
  int i, j, k, res = 0, tmp;

  if(dp[x1][x2][y1][y2] >= 0) return dp[x1][x2][y1][y2];

  rep(i,N) if(x[x1]<x[i] && x[i]<x[x2] && y[y1]<y[i] && y[i]<y[y2]){
    tmp = x[x2] - x[x1] + y[y2] - y[y1] - 3;
    tmp += solve(x1, i, y1, i);
    tmp += solve(x1, i, i, y2);
    tmp += solve(i, x2, y1, i);
    tmp += solve(i, x2, i, y2);
    res = max(res, tmp);
  }

  return dp[x1][x2][y1][y2] = res;
}

int main(){
  int i, j, k, l;
  int res;

  reader(&X, &Y);
  reader(&N);
  rep(i,N) reader(x+i, y+i);

  x[N] = 0; x[N+1] = X+1;
  y[N] = 0; y[N+1] = Y+1;

  rep(i,N+2) rep(j,N+2) rep(k,N+2) rep(l,N+2) dp[i][j][k][l] = -1;

  res = solve(N, N+1, N, N+1);

  writer(res, '\n');

  return 0;
}

Current time: 2017年07月28日23時44分31秒
Last modified: 2014年05月24日04時15分32秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC008 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: