utsubo’s blog

競技プログラミングとか.

ACM-ICPC 2016 国内予選 D : ダルマ落とし

問題

配列の隣り合った2つ要素の差が1以下であれば,その2つ要素を消すことができる.
この操作を繰り返す時,最適に消していくと,最大何個要素を消せるか.

例:{1,3,2,1}が与えられたとき
{1,3,2,1} -> {1,1} -> {}  ⇐4個消せる
{1,3,2,1} -> {1,3}    ⇐先に右端の要素の2,1を消すと,2個しか消せない

制約

配列の長さ <= 300
1 <= 要素の値 <= 1000

Daruma Otoshi | Aizu Online Judge

方針

dp[ l ][ r ] := [ l , r ]の区間で最大いくつ取り出せるか
とすると,

ある幅dに対して,
① {1,2,3,4} -> {x,x,o,o}
dp[ l ][ l + d ]より小さい区間のdpが求まっているとすると,
dp[ l ][ l + d ] = max{ dp[ l ][ k ] + dp[ k + 1 ][ l + d ] }
となりそう.

② {1,3,3,1} -> {1,x,x,1} -> {o,x,x,o}
dp[ l ][ l + d ] = d + 1 (oの間のxの要素が全部消えてる)
かつ
abs( x[ l - 1] - x[ l + d + 1] ) <= 1 (端にあるoの要素の差が1以下)
であれば,
dp[ l - 1 ][ l + d + 1 ] = d + 1 + 2 (間の要素数+2)
となりそう.

良い感じにループを回す.

コード

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

bool solve(){
	int n;
	cin >> n;
	if(n == 0)return false;
	vector<int> x(n);
	for(int i=0;i<n;i++)
		cin >> x[i];

	vector<vector<int>> dp(n+1,vector<int>(n+1));
	for(int i=0;i<n-1;i++){
		if( abs( x[i] - x[i+1] ) <= 1 )
			dp[i][i+1] = 2;
	}

	for(int d=1;d<n;d++){
		for(int l=0;l<n;l++){
			if( l + d >= n )continue;
			for(int r=l;r<l+d;r++){
				dp[l][l+d] = max(dp[l][l+d], dp[l][r] + dp[r+1][l+d]);
			}
			if( l - 1 >= 0 && l + d + 1 < n){
				if( dp[l][l+d] == d + 1 && abs( x[l-1] - x[l+d+1] ) <= 1 ){
					dp[l-1][l+d+1] = max(dp[l-1][l+d+1] ,dp[l][l+d] + 2);
				}
			}
		}
	}
	cout << dp[0][n-1] << endl;
	return true;
}

int main(void){
	while(solve()){}
	return 0;
}

半年放置したらなんとか解けた.