Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define S second
- #define F first
- using namespace std;
- const int MOD = 1e9;
- vector<int> a;
- int dp [2005][2005];
- int fans(int l, int r)
- {
- //cerr << l <<' '<< r << endl;
- if (l > r)
- return 0;
- int cran = 0;
- int fans1 = 0;
- int fans2 = 0;
- if (l == r)
- return dp[l][r] = 1;
- if (dp[l + 1][r - 1] == 0)
- cran = fans(l + 1, r - 1);
- else
- cran = dp[l + 1][r - 1];
- int dubalar = 0;
- if (dp[l + 1][r] == 0)
- fans1 = fans(l + 1, r);
- else
- fans1 = dp[l + 1][r];
- if (dp[l][r - 1] == 0)
- fans2 = fans(l, r - 1);
- else
- fans2 = dp[l][r - 1];
- if (a[l] == a[r])
- dubalar = (cran + 1) % MOD;
- return dp[l][r] = (((fans1 + fans2) % MOD - cran + MOD) % MOD + dubalar) % MOD;
- }
- int main() {
- // freopen("matching.in", "r", stdin);
- //freopen("matching.out", "w", stdout);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- dp[i][j] = 0;
- a.resize(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- fans(0, n - 1);
- cout << dp[0][n - 1] << endl;
- /* for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++)
- cout << dp[i][j] << ' ';
- cout << endl;
- }*/
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement