daily pastebin goal
63%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 42 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cmath>
  4. #include <math.h>
  5. #include <cstdio>
  6. #include <string>
  7. #include <algorithm>
  8. #include <functional>
  9. #include <stack>
  10. #include <list>
  11. #include <vector>
  12. #include <map>
  13. #include <set>
  14. #include <queue>
  15. #include <iomanip>
  16. #include <unordered_set>
  17. #include <unordered_map>
  18. #include <bitset>
  19. #include <regex>
  20. #include <sstream>
  21.  
  22. using namespace std;
  23.  
  24. const int mod = 1e9;
  25. int INF = 1e9;
  26.  
  27. int main() {
  28.     long long n;
  29.     cin >> n;
  30.     vector < long long > a(n);
  31.  
  32.     for (int i = 0; i < n; i++) {
  33.         cin >> a[i];
  34.     }
  35.  
  36.     vector < vector < long long > > dp(n, vector < long long >(n, 0));
  37.  
  38.     for (int i = 0; i < n; i++) {
  39.         dp[i][i] = 1;
  40.     }
  41.  
  42.     for (int i = 0; i < n - 1; i++) {
  43.         dp[i][i + 1] = 2;
  44.         if (a[i] == a[i + 1]) {
  45.             dp[i][i + 1]++;
  46.         }
  47.     }
  48.  
  49.     for (int len = 3; len <= n; len++) {
  50.         for (int i = 0; i < n; i++) {
  51.             int j = i + len - 1;
  52.             if (j >= n)
  53.                 continue;
  54.  
  55.             dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + mod) % mod;
  56.             if (a[i] == a[j]) {
  57.                 dp[i][j] += dp[i + 1][j - 1] + 1;
  58.             }
  59.             dp[i][j] %= mod;
  60.         }
  61.     }
  62.  
  63.     cout << dp[0][n - 1] % mod;
  64.     //system("pause");
  65. }
RAW Paste Data
Top