Untitled
unknown
c_cpp
a year ago
1.2 kB
4
Indexable
#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; }
Editor is loading...