Advertisement
Guest User

Untitled

a guest
Jun 30th, 2016
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. auto solve(int n, const vector<int>& w) -> int {
  5. vector<vector<int>> dp(n, vector<int>(n, 0));
  6. auto f = [&w](int l, int r) {return abs(w[l] - w[r]) <= 1 ? 2 : 0;};
  7. auto fm = [&](int l, int r) {return dp[l + 1][r - 1] + (dp[l + 1][r - 1] < r - l - 1 ? 0 : f(l, r));};
  8. auto fl = [&](int l, int r) {return dp[l][r - 2] + f(r - 1, r);};
  9. auto fr = [&](int l, int r) {return dp[l + 2][r] + f(l, l + 1);};
  10. for(auto l = 0, r = l + 1; l < n - 1; l++, r++) dp[l][r] = f(l, r);
  11. for(auto len = 3; len < n; len += 2)
  12. for(auto l = 0, r = l + len; l < n - len; l++, r++)
  13. dp[l][r] = max({dp[l][r], fm(l, r), fl(l, r), fr(l, r)});
  14. return max({dp[0][n - 1], dp[0][n - 2], dp[1][n - 1]});
  15. }
  16.  
  17. auto main() -> int {
  18. int n;
  19. while(cin >> n, n) {
  20. vector<int> w(n);
  21. for(auto& i : w) cin >> i;
  22. cout << solve(n, w) << endl;
  23. }
  24. return 0;
  25. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement