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個しか消せない
方針
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; }
半年放置したらなんとか解けた.