kmjp's blog

競技プログラミング参加記です

AtCoder ABC #145 : F - Laminate

方針が行ったり来たりしてしまったのが難点。
https://atcoder.jp/contests/abc145/tasks/abc145_f

問題

N列のグリッドがある。
i列目は下からH[i]行まで黒く塗られた状態にしたい。

N列中、K列までH[i]を任意に変化させられるとする。
そうして変形したグリッドについて、高さ1、横幅任意の矩形を使い、黒い部分を塗りつぶしたい。
最少何個の矩形を使えばよいか。

解法

H[1]~H[N]の手前にH[0]=0があると考えるとわかりやすい。
まず、H[i]をどう変化するとよいかを考えよう。
H[i]をH[i-1]と同じに合わせるようにすると、(i-1)列目とi列目は常に同じ矩形を使って塗りつぶせるので、i列目を調整するために矩形を追加する必要がなくなる。
言い換えると、i列目はなかったものとして考えられる。

よって、この問題はK列までをなかったものとすることに相当する。
また、a列目の次に残すものをb列目にするとき、max(0,H[b]-H[a])個の矩形が追加で必要になる。

dp(n,k) := prefixのうちn列目までを考え、かつn列目を最後に残す場合、あとk列まで消せる場合の必要な矩形の最小値。
とする。dp(0,K)=0から初めて
dp(n,k-(n-m-1)) = min(dp(m,k) + max(0,H[n]-H[m]))
で状態を更新していけばよい。

int N,K;
int H[303];

ll dp[303][303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	if(K==N) return _P("0\n");
	FOR(i,N) cin>>H[i+1];
	
	FOR(x,N+2) FOR(y,N+2) dp[x][y]=1LL<<60;
	dp[0][K]=0;
	ll mi=1LL<<60;
	
	FOR(i,N+1) {
		FOR(x,K+1) if(dp[i][x]<1LL<<60) {
			if(x>=N-i) mi=min(mi,dp[i][x]);
			for(y=i+1;y<=N&&x>=y-i-1;y++) {
				int dif=max(H[y]-H[i],0);
				dp[y][x-(y-i-1)]=min(dp[y][x-(y-i-1)],dp[i][x]+dif);
			}
		}
	}
	
	cout<<mi<<endl;
	
}

まとめ

コードは短いのよね。