Advertisement
Josif_tepe

Untitled

Apr 20th, 2023
676
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #include <queue>
  7. #include <algorithm>
  8. //#include <bits/stdc++.h>
  9. //#include <bits/stdc++.h>
  10.  
  11. using namespace std;
  12. const int maxn = 5050;
  13. bool is_palindrome[maxn][maxn];
  14. int dp[maxn][maxn];
  15. string s;
  16. int rec(int i, int j) {
  17.     if(i > j) {
  18.         return 0;
  19.     }
  20.     if(dp[i][j] != -1) {
  21.         return dp[i][j];
  22.     }
  23.     int result = 0;
  24.     if(is_palindrome[i][j]) {
  25.         result = 1;
  26.     }
  27.     result += rec(i + 1, j) + rec(i, j - 1) - rec(i + 1, j - 1);
  28.     return dp[i][j] = result;
  29. }
  30. int main() {
  31.     ios::sync_with_stdio(0);
  32.     cin >> s;
  33.     int n = s.size();
  34.     memset(is_palindrome, false, sizeof is_palindrome);
  35.     memset(dp, -1, sizeof dp);
  36.     for(int sz = 1; sz <= n; sz++) {
  37.         for(int at = 0; at <= n - sz; at++) {
  38.             if(sz <= 2) {
  39.                 if(s[at] == s[at + sz - 1]) {
  40.                     is_palindrome[at][at + sz - 1] = true;
  41.                 }
  42.             }
  43.             else if(s[at] == s[at + sz - 1]) {
  44.                 is_palindrome[at][at + sz - 1] = is_palindrome[at + 1][at + sz - 2];
  45.             }
  46.            
  47.         }
  48.     }
  49.     for(int i = 0; i < n; i++) {
  50.         dp[i][i] = 1;
  51.     }
  52.     for(int i = 0; i + 1 < n; i++) {
  53.         if(s[i] == s[i + 1]) {
  54.             dp[i][i + 1] = 3;
  55.         }
  56.         else {
  57.             dp[i][i + 1] = 2;
  58.         }
  59.     }
  60.     rec(0, n - 1);
  61.     int t;
  62.     cin >> t;
  63.     while(t--) {
  64.         int L, R;
  65.         cin >> L >> R;
  66.         cout << dp[L - 1][R - 1] << "\n";
  67.     }
  68.     return 0;
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement