Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
1.2 kB
0
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i : a) {
        cin >> i;
    }
    auto can = [&](int l, int r) -> bool {
        stack<int> st;
        for (int i = l; i <= r; i++) {
            int cur = a[i];
            while (!st.empty() && cur == st.top()) {
                st.pop();
                cur++;
            }
            st.push(cur);
        }
        if (st.size() == 1) {
            return true;
        } else {
            return false;
        }
    };
    vector<int> p(n + 1);
    p[0] = 0;
    for (int r = 0; r < n; r++) {
        p[r + 1] = r + 1;
        for (int l = 0; l <= r; l++) {
            //debug(l, r, can(l, r));
            if (can(l, r)) {
                p[r + 1] = min(p[r + 1], p[l] + 1);
            }
        }
    }
    cout << p[n];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}