Educational Codeforces Round 83 E - Array Shrinking

問題ページ

幅が小さい区間から順に参照していくようなDPである、区間DPをします。

区間 をマージするときに操作を行って長さを減少させるのは、 が両方とも長さ1で、値が同じときだけ考えればよいです。これ以外のときに に操作を行うようなことを考慮しなくても大丈夫です。なぜなら、DPの遷移的にすでに に操作を行うような列について考えているからです。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    vector<vector<ll>> dp(n, vector<ll>(n, INF));  
    vector<vector<ll>> val(n, vector<ll>(n, -1));  
    REP(i, n) dp[i][i] = 1, val[i][i] = a[i];  
    FOR(w, 2, n+1) REP(l, n-w+1) {  
        ll r = l+w-1;  
        FOR(i, l, r) {  
            if(dp[l][i] == 1 && dp[i+1][r] == 1 && val[l][i] == val[i+1][r]) {  
                chmin(dp[l][r], 1LL);  
                val[l][r] = val[l][i] + 1;  
            } else {  
                chmin(dp[l][r], dp[l][i] + dp[i+1][r]);  
            }  
        }  
    }  
    cout << dp[0][n-1] << endl;  
  
    return 0;  
}