fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5.  
  6. int solveOne(int i, int j, string s, int **ispalindrome){
  7.  
  8.  
  9.    if(i > j) return 0;
  10.  
  11.  
  12.  
  13.    if(i == j)  return ispalindrome[i][j] = 1;
  14.  
  15.    if(ispalindrome[i][j] != 0) return ispalindrome[i][j];  
  16.  
  17.    if(s[i] ==  s[j]){
  18.  
  19.       int mid = j-i-1;
  20.  
  21.       if(j==i+1) {
  22.       	ispalindrome[i][j]=1;
  23.       	return 2;
  24.       }
  25.  
  26.       if(mid == solveOne(i+1, j-1, s, ispalindrome)){
  27.             ispalindrome[i][j] = 1;
  28.             return 2+ mid;
  29.       }
  30.  
  31.       else
  32.         return ispalindrome[i][j] = 0;
  33.    }
  34.    return 0;
  35. }
  36.  
  37.  
  38.  
  39. int solveTwo(int i, int j, string s,int **dp, int &count , int **ispalindrome){
  40.  
  41.   // cout<<"inside solve two"<<endl;
  42.  
  43.     if(i > j) return 0;
  44.  
  45.     if(i == j) return dp[i][j] = 1;
  46.  
  47.      if(dp[i][j] != 0) return dp[i][j];
  48.  
  49.      count++;
  50.  
  51.  
  52.     return dp[i][j] = solveTwo(i+1, j, s,dp , count , ispalindrome) + solveTwo(i, j-1, s ,dp , count , ispalindrome) + (ispalindrome[i][j] != 0 ? 1 : 0) - solveTwo(i+1, j-1, s ,dp , count , ispalindrome);
  53.  
  54. }
  55.  
  56.  
  57. int main()
  58. {
  59.  
  60.           #ifndef ONLINE_JUDGE
  61.     freopen("input.txt", "r", stdin);
  62.     freopen("output.txt", "w", stdout);
  63.    #endif
  64.  
  65. string s; cin>>s;
  66. int len = s.length();
  67.  
  68. int **dp = new int*[len];
  69. for(int i=0;i<len;i++){
  70.     dp[i] = new int[len];
  71.     for(int j = 0; j<len;j++)
  72.         dp[i][j] = 0;
  73. }
  74.  
  75.  
  76. int **ispalindrome = new int*[len];
  77. for(int i=0;i<len;i++){
  78.     ispalindrome[i] = new int[len];
  79.     for(int j = 0; j<len;j++){
  80.      ispalindrome[i][j] = 0;
  81.      if(i==j) ispalindrome[i][j] = 1;
  82.    }
  83. }
  84.  
  85.  
  86.  
  87. int count = 0;
  88. for(int i=0; i<len; i++) {
  89. 	for(int j=0; j<len; j++){
  90. 		solveOne(i, j, s, ispalindrome);
  91. 	}
  92. }
  93.  solveTwo(0,len-1,s,dp , count , ispalindrome);
  94.    cout<<endl<<endl;
  95.    for(int i=0;i<len;i++){
  96.          for(int j=0;j<len;j++){
  97.     cout<<setw(3)<<dp[i][j]<<" ";
  98.    }
  99.         cout<<endl;
  100. }
  101.  
  102.    cout<<endl<<endl;
  103.    for(int i=0;i<len;i++){
  104.          for(int j=0;j<len;j++){
  105.     cout<<setw(3)<<ispalindrome[i][j]<<" ";
  106.    }
  107.         cout<<endl;
  108. }
  109.  
  110.  
  111. int n; cin>>n;
  112. for(int i=0;i<n;i++){
  113. int l,r; cin>>l>>r;
  114.  
  115. cout<<dp[l-1][r-1]<<endl;
  116.  
  117. }
  118.  
  119. cout<<endl<<endl<<count;
  120.     return 0;
  121. }
  122.  
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
aaaaa
3
1 3
1 1
1 2
stdout
copy 

  1   3   6  10  15 
  0   1   3   6  10 
  0   0   1   3   6 
  0   0   0   1   3 
  0   0   0   0   1 


  1   1   1   1   1 
  0   1   1   1   1 
  0   0   1   1   1 
  0   0   0   1   1 
  0   0   0   0   1 
6
1
3


10
https://ideone.com/6PjUO0
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!