intさわだんのBlack History

刹那的レジェンドになりたい。

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

パッと見シミュレーションか貪欲法かなと思って考えていたが一向に解法が浮かばなかったので解説を見ました。DPという発想が出てこなかった。こういう問題がでたら確実に通したい。

解法:

  • 2個、4個、6個....連続で取り除けるかの情報をdp1[i][j]に保存する。j-iは偶数。dp1[1][4]が4の場合1,2,3,4番目のブロックは連続してすべて取り除けるということ。
  • dp2[i] = (dp2[k] + dp1[k+1][i]を0~k~iの範囲でfor文で回し、その中の最大値)

というようにすればよい。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int dp1[310][310];
int dp2[310];

int main(){
    int n,w[310];

    while(true){
        cin >> n;
        if(n == 0)break;
        for(int i = 0;i < 305;i++){ //初期化
            dp2[i] = 0;
            for(int j = 0;j < 305;j++){
                dp1[i][j] = 0;
            }
        }
        for(int i = 0;i < n;i++)cin >> w[i];
        for(int len = 1;len < n;len+=2){
            for(int i = 0;i+len < n;i++){
                int j = i + len;
                if(abs(w[i]-w[j]) <= 1 && (len == 1 || dp1[i+1][j-1] != 0)){
                    dp1[i][j] = dp1[i+1][j-1] + 2;
                }else{
                    for(int k = 1;i+k < j-1;k++){
                        if(dp1[i][i+k] != 0 && dp1[i+k+1][j] != 0){
                            dp1[i][j] = len+1;
                        }
                    }
                }
            }
        }
        for(int i = 1;i < n;i++){
            dp2[i] = dp1[0][i];
            for(int j = 0;j < i;j++){
                dp2[i] = max(dp2[i],dp2[j]+dp1[j+1][i]);
            }
        }
        cout << dp2[n-1] << endl;
    }
}