Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- auto solve(int n, const vector<int>& w) -> int {
- vector<vector<int>> dp(n, vector<int>(n, 0));
- auto f = [&w](int l, int r) {return abs(w[l] - w[r]) <= 1 ? 2 : 0;};
- auto fm = [&](int l, int r) {return dp[l + 1][r - 1] + (dp[l + 1][r - 1] < r - l - 1 ? 0 : f(l, r));};
- auto fl = [&](int l, int r) {return dp[l][r - 2] + f(r - 1, r);};
- auto fr = [&](int l, int r) {return dp[l + 2][r] + f(l, l + 1);};
- for(auto l = 0, r = l + 1; l < n - 1; l++, r++) dp[l][r] = f(l, r);
- for(auto len = 3; len < n; len += 2)
- for(auto l = 0, r = l + len; l < n - len; l++, r++)
- dp[l][r] = max({dp[l][r], fm(l, r), fl(l, r), fr(l, r)});
- return max({dp[0][n - 1], dp[0][n - 2], dp[1][n - 1]});
- }
- auto main() -> int {
- int n;
- while(cin >> n, n) {
- vector<int> w(n);
- for(auto& i : w) cin >> i;
- cout << solve(n, w) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement