simushin_pavel

Untitled

Nov 30th, 2020
494
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3. const long long SIZE=2E3+5;
  4. long long dp[SIZE][SIZE]={-1}, a[SIZE];
  5. long long f(long long l, long long r){
  6.     if(l==r){
  7.         dp[l][r]=1;
  8.         return 1;
  9.     }
  10.     if(dp[l][r]!=-1) return dp[l][r];
  11.     dp[l][r]=f(l+1, r)+f(l, r-1)+f(l+1, r-1);
  12.     if(a[l]==a[r]) dp[l][r]+=1+f(l+1, r-1);
  13.     return dp[l][r];
  14. }
  15. int main(){
  16.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  17.     long long n, i, j; cin >> n; for(i=0; i<n; ++i) cin >> a[i];
  18.     for(i=0; i<n; ++i) dp[i][i]=a[i];
  19.     cout << f(0, n-1);
  20.     return 0;
  21. }
RAW Paste Data