問題概要

n$( n \leq 300)$ 個のブロックが重なったダルマ落としがある． i 番目のブロックの重さは $w_i ( w_i \leq 1000)$ である．

このブロックを2個ずつ叩き出して (1個だけ叩き出す，3個以上同時に叩き出すことはできない) ，できるだけ多くのブロックを叩き出せるようにしたい．ただし，隣り合った2個のブロックを叩き出すには，2個のブロックの重さの差の絶対値が1以下でなければならない．

各テストケース (テストケースは 50以下) について，叩き出せるブロックの数の最大値を求めよ．

解法概要

ある2個のブロックを叩き出せるパターンは，

もともと隣り合っているブロックの重さの差の絶対値が1以下
もともと隣り合ってはいないが，ブロックの重さの差の絶対値が1以下でかつそのペアの間に挟まっているブロックがすべて叩き出せる

のみなので，区間 DP で行けそうな気持ちになる．

ほとんどソースコードのコメントに書いてしまったので，ここに書くことがあまりない．

ソースコード

再帰の方がシンプルに書けるかな〜と思ったけど個人的にはあんまり変わらなかった．再帰版はこれ

#include <iostream>
#include <cmath>

using namespace std;

void solve(int n) {
    int w[n];
    for(int i=0;i<n;++i){
        cin >> w[i];
    }

    int dp[n+1][n+1];
    // dp[i][j] := i を先頭とした j 個のブロックがあるとして，消せるブロックの数の最大値
    fill_n(dp[0], (n+1)*(n+1), 0);

    for(int j=2;j<=n;++j) {
        for(int i=0;i<=n-j;++i) {
            // あるペアの差の絶対値が1以下で，ペアの間の数が全て消せていたら，
            // そのペアを含めた区間も全て消せる
            if(abs(w[i]-w[i+j-1]) <= 1 && dp[i+1][j-2] == j-2) {
                dp[i][j] = j;
                continue;
            }
            
            // 区間を途中で区切って最大の場合を見つける
            for(int k=i;k<=i+j;++k) {
                dp[i][j] = max(dp[i][j], dp[i][k-i] + dp[k][i+j-k]);
            }
        }
    }

    cout << dp[0][n] << endl;
}

int main() {
    int n;
    while(cin >> n && n) solve(n);
}

NoiminのNoise

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

問題概要

解法概要

ソースコード

所感